1. Library und Data
library(tidyverse)
library(dplyr)
library(data.table)
library(ggplot2)
library(reshape2)
library(rsample)
library(recommenderlab)
data(MovieLense)
  1. Explorative Datenanalyse
mx_user_film <- as(MovieLense, "matrix")  # convert realratingmatrix to normal matrix
df_user_film <- as.data.frame(mx_user_film)   #  convert matrix to dataframe form
df_film_user <- as.data.frame(t(mx_user_film)) # transpose the dataframe: each row is a movie name, each column is a user

2.1 Welches sind die am häufigsten geschauten Genres/Filme?

df_21 <- df_film_user %>% mutate(cnt = rowSums(!is.na(df_film_user))) %>% arrange(desc(cnt)) %>% filter(cnt == max(cnt)) %>% select('cnt')
df_21

Die am häufigsten geschauten Filme ist Star Wars.

2.2 Wie verteilen sich die Kundenratings gesamthaft und nach Genres?

df_unlist <- data.frame(rating=unlist(df_film_user))            # unlist the dataframe
ggplot(df_unlist,aes(rating)) + geom_histogram() +                # die Verteilung der Kundenratings gesamthaft
  labs(x="Ratings", y="Count",title="Distribution of the user ratings") +
  theme(plot.title = element_text(hjust = 0.5))
`stat_bin()` using `bins = 30`. Pick better value with `binwidth`.
Warning: Removed 1469760 rows containing non-finite values (stat_bin).

The above histogram of ratings distribution is left skewed, with the mode = 4.

mx_film_genre <- as.data.frame(MovieLenseMeta) 
rownames(mx_film_genre) <- mx_film_genre$title
mx_film_genre <- as.matrix(mx_film_genre[,5:22])   # Movie Genre Matrix

mx_user_film[is.na(mx_user_film)] <- 0

mx_user_genre <- mx_user_film %*% mx_film_genre

mx_genre_user <- as.data.frame(t(mx_user_genre))    # a: Stärke Genre Kombination vollständig
mx_genre_user$summe <- rowSums(mx_genre_user)               # new column "summe": summe user ratings of each genre
mx_genre_user <- cbind(genre = rownames(mx_genre_user), mx_genre_user)# new column "genre": genre name copied from rownames
ggplot(mx_genre_user,aes(summe,genre)) + geom_col() + labs(x= "summed ratings of all users", y="Genre",title="Distribution of the user ratings by genre combination") + 
  theme(plot.title = element_text(hjust = 0.5))

mx_genre_user <- mx_genre_user %>% select(-genre)

Above is the distribution of ratings by genre, “drama” has the highest summed ratings.

df_22 <- as.data.frame(t(mx_film_genre)) %>% mutate(cnt = rowSums(as.data.frame(t(mx_film_genre))))%>% arrange(desc(cnt))  # add new column: count for each genres
df_22 <- cbind(genres = rownames(df_22),df_22)               # index as a column
rownames(df_22) <- 1:nrow(df_22)                            # generate new index

ggplot(df_22,aes(x = (reorder(genres,cnt)), y = cnt)) + geom_col() + coord_flip() +
  labs(y="Number of Views", x="Genres",title="Distribution by genres") + 
  theme(plot.title = element_text(hjust = 0.5))

The plot above shows the distribution of views by genre. The genre drama has the highest number of views.

2.3 Wie verteilen sich die mittleren Kundenratings pro Film?

df_avg_rating_film <- df_film_user %>% mutate(avg_rating = rowMeans(df_film_user,na.rm = TRUE, dims = 1)) %>% select('avg_rating')
ggplot(df_avg_rating_film,aes(avg_rating)) + geom_histogram(binwidth = 1) +                # die Verteilung
  labs(x="Mean user-ratings per film", y="Count of films",title="Distribution of the mean user-ratings per film") + 
  theme(plot.title = element_text(hjust = 0.5))

The plot showed us that the mode of average ratings per film is 3. Most of movies have the average rating larger than 2.

2.4 Wie stark streuen die Ratings von individuellen Kunden?

df_avg_rating_user <- df_user_film %>% mutate(avg_rating = rowMeans(df_user_film,na.rm = TRUE, dims = 1)) %>% select('avg_rating')
ggplot(df_avg_rating_user,aes(avg_rating)) + geom_histogram(bins = 5) +                # die Verteilung
  labs(x="Mean user-ratings per user", y="Count of users",title="Distribution of the mean user-ratings per user")+ 
  theme(plot.title = element_text(hjust = 0.5))

The plot shows the mode of average user ratings per user is 3. Most of the average ratings are 3 or 4.

2.5 Welchen Einfluss hat die Normierung der Ratings pro Kunde auf deren Verteilung?

df_avg_rating_user <- df_user_film %>% mutate(avg_rating = rowMeans(df_user_film,na.rm = TRUE, dims = 1)) %>% select('avg_rating')
ggplot(df_avg_rating_user,aes(avg_rating)) + geom_histogram(bins = 20) +                # die Verteilung
  labs(x="Mean ratings per user", y="Count of users",title="Distribution of the mean ratings per user")+ 
  theme(plot.title = element_text(hjust = 0.5))

normalized_movielens <- as(normalize(MovieLense,method = "z-score"), "matrix")
normalized_movielens <- as.data.frame(normalized_movielens)
normalized_avg_rating_user <- normalized_movielens %>% mutate(avg_rating=rowMeans(normalized_movielens,na.rm=TRUE, dims=1)) %>% select('avg_rating')  

ggplot(normalized_avg_rating_user,aes(avg_rating)) + geom_histogram(bins = 20) +                # die Verteilung
  labs(x="Mean normalized ratings per user", y="Count of users",title="Distribution of the mean normalized ratings per user") + 
  theme(plot.title = element_text(hjust = 0.5))

without normalization (first plot): the average ratings are slightly left skewed, with the mode of 3.8. The ratings vary a lot across different users.

with Z-score normalization (second plot): the average ratings per user are all around 0. This mean, the ratings from different users are normalized to the same scale, with the mean of 0, the standard deviation of 1. This will reduce the influence of rating habits of different users.

2.6 Welche strukturellen Charakteristika (z.B. Sparsity) und Auffälligkeiten zeigt die User-Item Matrix?

Recommender System data usually contains a large numbers of users(rows) and items (columns), but a single user interacts with only a small subset of the items. This means, the dataframe consists of many zero values, the structure is extremely sparse.

The User-Item Matrix of MovieLense dataset is dgCMatrix, which is a class of sparse numeric matrices in the compressed, sparse, column-oriented format. In this implementation the non-zero elements in the columns are sorted into increasing row order.

3 Datenreduktion

3.1 Reduziere den MovieLense Datensatz auf rund 400 Kunden und 700 Filme, indem du Filme und Kunden mit sehr wenigen Ratings entfernst.

df_reduced <- df_film_user %>% mutate(n_pro_film = rowSums(!is.na(df_film_user))) %>% arrange(desc(n_pro_film)) %>% slice(0:700)%>% select(-n_pro_film)       # reduce to 700 movies
df_reduced <- as.data.frame(t(df_reduced)) 
df_reduced <- df_reduced %>% mutate(n_pro_user = rowSums(!is.na(df_reduced))) %>% arrange(desc(n_pro_user)) %>% slice(0:400) %>% select(-n_pro_user)  # reduce to 400 users
df_reduced   # with 400 users and 700 films.

3.2 Untersuche und dokumentiere die Eigenschaften des reduzierten Datensatzes und beschreibe den Effekt der Datenreduktion: Anzahl Filme und Kunden sowie Sparsity vor und nach Datenreduktion

Vor Datenreduktion: 1664 Movies, 943 users, 93.82% Data are NA.

print(dim(df_user_film))
[1]  943 1664
print(sum(is.na(df_user_film))/(1663*942))
[1] 0.9382169
image(as(df_user_film,"matrix"), main = "sparsity of dataframe before reduction")

Nach Datenreduktion: 700 Movies, 400 users, 75.90% data are NA.

print(dim(df_reduced))
[1] 400 700
print(sum(is.na(df_reduced))/(700*400))
[1] 0.7589929
image(as(df_reduced,"matrix"),main = "sparsity of dataframe after reduction")

The two images above showed us the data sparsity before (first image) and after (second image) reduction. The blank pixels represent the NA, the color pixels represent the available values. By comparing the two images, we could see that the first image has more blank and less color pixels than the second one. This means the data after reduction is less sparse than before reduction. Data reduction has successfully reduced the data sparsity.

3.3 mittlere Kundenratings pro Film vor und nach Datenreduktion.

Before data reduction

df_avg_rating <- df_film_user %>% mutate(avg_rating = rowMeans(df_film_user,na.rm = TRUE, dims = 1)) %>% select('avg_rating')
ggplot(df_avg_rating,aes(avg_rating)) + geom_histogram(binwidth = 0.25) +                # die Verteilung
  labs(x="Mean ratings per film", y="Count",title="Before reduction: Distribution of the mean ratings by film") + 
  theme(plot.title = element_text(hjust = 0.5))

df_reduced_t <- as.data.frame(t(df_reduced))
df_reduced_avg_rating <- df_reduced_t%>% mutate(avg_rating = rowMeans(df_reduced_t,na.rm = TRUE, dims = 1)) %>% select('avg_rating')
ggplot(df_reduced_avg_rating,aes(avg_rating)) + geom_histogram(binwidth = 0.25) +                # die Verteilung
  labs(x="Mean ratings per film", y="Count",title="After reduction: Distribution of the mean ratings by film") + 
  theme(plot.title = element_text(hjust = 0.5))

After the data reduction, the average ratings are close to a left skewed normal distribution.

4 Analyse Ähnlichkeitsmatrix

4.1 Zerlege den reduzierten MovieLense Datensatz in ein disjunkte Trainings-und Testdatenset im Verhältnis 4:1

set.seed(465)
mx_reduced <- as.matrix(df_reduced)
rrm_reduced <- as(mx_reduced,"realRatingMatrix")
train_test <- evaluationScheme(rrm_reduced, method="split", train=0.8, k=1, given=20, goodRating=4)

# training data 80% of the users
rrm_reduced_train <- getData(train_test,"train")


# test data is 20% of the all users, the test data is splited into two parts: known test data and unknown test data

# the known portion returns specified 20 items per test user is used to predict ratings or films for the test users
rrm_reduced_known <- getData(train_test,"known")


# the unknown portion is used to compute the prediction error of the model
rrm_reduced_unknown <- getData(train_test,"unknown")

4.2 Trainiere ein IBCF Modell mit 30 Nachbarn und Cosine Similarity

model_IBCF <- Recommender(data = rrm_reduced_train,method="IBCF",parameter=list(normalize = "Z-score",method="Cosine",k=30)) 

4.3 Bestimme die Verteilung der Filme, welche bei IBCF für paarweise Ähnlichkeitsvergleiche verwendet werden. Determine the distribution of films used in IBCF for pairwise similarity comparisons

# Here only exhibit the first 50 rows and columns
get_model_IBCF <- getModel(model_IBCF) 
image(get_model_IBCF$sim[1:50, 1:50], main = "Similarity of the first 50 rows and columns")

The similarity matrix is not symmetric. Each row has 30 elements larger than 0. In each column, the number of elements greater than 0 indicates how many times this film was included in the TOP list of other films.

IBCF_sim <- as.data.frame(colSums(get_model_IBCF$sim > 0)) 
colnames(IBCF_sim) <- "recommended_frequency" # frequency that the corresponding film is included in other films' TOP-N lists

ggplot(IBCF_sim, aes(x=IBCF_sim$recommended_frequency))+geom_histogram(fill="black", col="grey",binwidth = 5)+
  labs(x = "Recommended frequency", y = "Count", title = "Distribution of recommended frequency per film") +
  theme(plot.title = element_text(hjust = 0.5))
Warning: Use of `IBCF_sim$recommended_frequency` is discouraged. Use `recommended_frequency` instead.

The plot displays the distribution of films by how many times the corresponding film included in the TOP list of other films. For instance, about 52 films are not included in any TOP list of other films, about 100 films are included in the TOP lists of 5 films. The highest frequency is about 160.

4.4 Bestimme die Filme, die am häufigsten in der Cosine-Ähnlichkeitsmatrix auftauchen und analysiere deren Vorkommen und Ratings im reduzierten Datensatz.

die am häufigsten Film in der Cosine-Ähnlichkeitsmatrix

# die 10 am häufigsten Filme in der Cosine Ähnlichkeitsmatrix, i.e. die Filme mit der höheste sum Ähnlichkeits
high_freq_film <- IBCF_sim %>% mutate(film = rownames(IBCF_sim)) %>% arrange(desc(recommended_frequency)) %>% slice(0:10)  %>% select(film,recommended_frequency)
high_freq_film 

die Vorkommen und Ratings in reduzierten Datensatz

t <- df_reduced_t %>% mutate(is_NA = rowSums(is.na(df_reduced_t)),not_NA = rowSums(!is.na(df_reduced_t)),occurrence = rowSums(!is.na(df_reduced_t))/dim(df_reduced_t)[2], film = rownames(df_reduced_t)) %>% select(is_NA,not_NA,occurrence,film)
Occurrence <- left_join(high_freq_film,t,by = "film") %>% select(film,recommended_frequency,occurrence) 
t2 <- df_reduced_t %>% mutate(film = rownames(df_reduced_t), avg_rating = rowMeans(df_reduced_t,na.rm=TRUE))%>% select(film,avg_rating)
Occurrence <- left_join(Occurrence,t2,by = "film")
Occurrence  # occurrence: not_NA / user number, the user ratio that rated this film

occurrence: ratio that the film is rated to all users

avg_rating: the average rating of each film

From above the result for first two users, we could see that the top 15 recommendations for the same user between the IBCF and UBCF models are completely different.

Compare the top 15 recommendations for all test users First identify the most recommended movies in the TOP-15 list from all test users.

# generate frequency tables : all the recommendation films with the corresponding frequencies 

film_freq_IBCF <- as.data.frame(table(as.factor(TOP15_IBCF))) 
colnames(film_freq_IBCF) <- c("Film_by_IBCF", "Frequency") 

film_freq_UBCF <- as.data.frame(table(as.factor(TOP15_UBCF)))
colnames(film_freq_UBCF) <- c("Film_by_UBCF", "Frequency")

head(film_freq_IBCF %>% arrange(desc(Frequency)),15)
head(film_freq_UBCF %>% arrange(desc(Frequency)),15)
ggplot(head(film_freq_IBCF %>% arrange(desc(Frequency)),15),aes(x = reorder(Film_by_IBCF,Frequency), y = Frequency)) + geom_col() + coord_flip() +
  labs(y="Frequency", x="Film",title="Distribution of the Top-15 films for all the users with IBCF") + 
  theme(plot.title = element_text(hjust = 0.5))

ggplot(head(film_freq_UBCF %>% arrange(desc(Frequency)),15),aes(x = reorder(Film_by_UBCF,Frequency), y = Frequency)) + geom_col() + coord_flip() +
  labs(y="Frequency", x="Film",title="Distribution of the Top-15 films for all the users with UBCF") + 
  theme(plot.title = element_text(hjust = 0.5))

the UBCF model with ordinal ratings and cosine similarity has better accuracy.

6.2 Vergleiche den Anteil übereinstimmender Empfehlungen der Top 15 Liste für IBCF vs UBCF, beide mit binärem Rating und Jaccard Similarity für alle Testkunden

# convert the reduced dataset to binary: ratings > 3 converted as 1, ratings <= 3 converted as 0 
df_reduced_bi <- df_reduced
df_reduced_bi[df_reduced_bi <= 3] <- 0
df_reduced_bi[df_reduced_bi > 3] <- 1

set.seed(468)
mx_reduced_bi <- as.matrix(df_reduced_bi)
rrm_reduced_bi <- as(mx_reduced_bi,"realRatingMatrix")
train_test_bi <- evaluationScheme(rrm_reduced_bi, method="split", train=0.8, k=1, given=20)

# training data 80% of the users
rrm_reduced_train_bi <- getData(train_test_bi,"train")

# test data is 20% of the all users, the test data is splited into two parts: known test data and unknown test data
# the known portion returns specified 20 items per test user is used to predict ratings or films for the test users
rrm_reduced_known_bi <- getData(train_test_bi,"known")

# the unknown portion is used to compute the prediction error of the model
rrm_reduced_unknown_bi <- getData(train_test_bi,"unknown")

# train the IBCF or UBCF model on training dataset
model_IBCF_bi <- Recommender(data = rrm_reduced_train_bi,method="IBCF",parameter=list(normalize = "Z-score",method="Jaccard",k=30))
model_UBCF_bi <- Recommender(data = rrm_reduced_train_bi,method="UBCF",parameter=list(normalize = "Z-score",method="Jaccard",nn=30))

# predict the ratings of test users by IBCF and UBCF
pred_rating_IBCF_bi <- as(predict(object = model_IBCF_bi, newdata = rrm_reduced_known_bi, n = 15,type="ratings"),"matrix")
pred_rating_UBCF_bi <- as(predict(object = model_UBCF_bi, newdata = rrm_reduced_known_bi, n = 15,type="ratings"),"matrix")

# the test user "unknown" ratings
mx_reduced_unknown_bi <- as(rrm_reduced_unknown_bi,"matrix")

# evaluate recommendations on "unknown" ratings
acc_IB_bi <- calcPredictionAccuracy(predict(object = model_IBCF_bi, newdata = rrm_reduced_known_bi, n = 15,type="ratings"),rrm_reduced_unknown_bi)
acc_UB_bi <- calcPredictionAccuracy(predict(object = model_UBCF_bi, newdata = rrm_reduced_known_bi, n = 15,type="ratings"),rrm_reduced_unknown_bi)
acc_bi <- rbind(acc_IB_bi,acc_UB_bi)
rownames(acc_bi) <- c("IBCF binary","UBCF binary")
acc_bi
                 RMSE       MSE       MAE
IBCF binary 0.6302688 0.3972388 0.3976143
UBCF binary 0.4748717 0.2255031 0.3975344

the UBCF model with binary ratings and cosine similarity has better accuracy.

6.3 Vergleiche den Anteil übereinstimmender Empfehlungen der Top 15 Liste für UBCF mit ordinalem (Cosine Similarity) vs binärem Rating (Jaccard Similarity) für alle Testkunden.

rbind(acc_ordinal,acc_bi)
                  RMSE       MSE       MAE
IBCF ordinal 1.2921763 1.6697195 0.9504537
UBCF ordinal 1.0734398 1.1522730 0.8403449
IBCF binary  0.6302688 0.3972388 0.3976143
UBCF binary  0.4748717 0.2255031 0.3975344

The model with binary ratings have largely improved the accuracy comparing to the models with ordinal ratings.

7 Analyse Top-N Listen -IBCF vs SVD Aufgabe: Vergleiche Memory-based IBCF und Modell-based SVD Recommenders bezüglich Überschneidung ihrer Top-N Empfehlungen für die User-Item Matrix des reduzierten Datensatzes (Basis: IBCF mit 30 Nachbarn und Cosine Similarity).

  1. Vergleiche wie sich der Anteil übereinstimmender Empfehlungen der Top-15 Liste für IBCF vs verschiedene SVD Modelle verändert, wenn die Anzahl der Singulärwerte für SVD von 10 auf 20, 30, 40, 50 verändert wird.

# SVD MODEL
model_SVD_10 <- Recommender(data = rrm_reduced_train,method="SVD",parameter=list(normalize = "Z-score",k=10))
model_SVD_20 <- Recommender(data = rrm_reduced_train,method="SVD",parameter=list(normalize = "Z-score",k=20))
model_SVD_30 <- Recommender(data = rrm_reduced_train,method="SVD",parameter=list(normalize = "Z-score",k=30))
model_SVD_40 <- Recommender(data = rrm_reduced_train,method="SVD",parameter=list(normalize = "Z-score",k=40))
model_SVD_50 <- Recommender(data = rrm_reduced_train,method="SVD",parameter=list(normalize = "Z-score",k=50))

# evaluate recommendations on "unknown" ratings
acc_SVD_10 <- calcPredictionAccuracy(predict(object = model_SVD_10, newdata = rrm_reduced_known, n = 15,type="topNList"),rrm_reduced_unknown,given=20,goodRating = 4)
acc_SVD_20 <- calcPredictionAccuracy(predict(object = model_SVD_20, newdata = rrm_reduced_known, n = 15,type="topNList"),rrm_reduced_unknown,given=20,goodRating = 4)
acc_SVD_30 <- calcPredictionAccuracy(predict(object = model_SVD_30, newdata = rrm_reduced_known, n = 15,type="topNList"),rrm_reduced_unknown,given=20,goodRating = 4)
acc_SVD_40 <- calcPredictionAccuracy(predict(object = model_SVD_40, newdata = rrm_reduced_known, n = 15,type="topNList"),rrm_reduced_unknown,given=20,goodRating = 4)
acc_SVD_50 <- calcPredictionAccuracy(predict(object = model_SVD_50, newdata = rrm_reduced_known, n = 15,type="topNList"),rrm_reduced_unknown,given=20,goodRating = 4)

acc_IBCF_top15 <- calcPredictionAccuracy(predict(object = model_IBCF, newdata = rrm_reduced_known, n = 15,type="topNList"),rrm_reduced_unknown,given=20,goodRating = 4)

acc_SVD_IB <- rbind(acc_SVD_10,acc_SVD_20,acc_SVD_30,acc_SVD_40,acc_SVD_50,acc_IBCF_top15)
rownames(acc_SVD_IB) <- c("SVD_k_10","SVD_k_20","SVD_k_30","SVD_k_40","SVD_k_50","IBCF_cos_k_30")
acc_SVD_IB
                  TP     FP      FN       TN   N precision     recall        TPR        FPR
SVD_k_10      6.8375 8.1625 74.5500 590.4500 680 0.4558333 0.09185763 0.09185763 0.01346130
SVD_k_20      6.0625 8.9375 75.3250 589.6750 680 0.4041667 0.07887917 0.07887917 0.01478280
SVD_k_30      5.9250 9.0750 75.4625 589.5375 680 0.3950000 0.07734909 0.07734909 0.01500427
SVD_k_40      6.0250 8.9750 75.3625 589.6375 680 0.4016667 0.07828355 0.07828355 0.01484067
SVD_k_50      5.5375 9.4625 75.8500 589.1500 680 0.3691667 0.07166389 0.07166389 0.01567906
IBCF_cos_k_30 5.7875 9.2125 75.6000 589.4000 680 0.3858333 0.07194244 0.07194244 0.01518621

The model with SVD and 10 neighbors have the best precision and recall.

SVD k=10 > SVD k=20 > SVD k=40 > SVD k=30 > IBCF cosine k=30 > SVD k=50

8 Wahl des optimalen Recommenders Aufgabe: Bestimme aus 5 unterschiedlichen Modellen das hinsichtlich Top-N Empfehlungen beste Modell. Begründe deine Modellwahlen aufgrund der bisher gemachten Erkenntnisse und verwende als 6. Modell einen Top-Movie Recommender (Basis: reduzierter Datensatz).

8.1 Verwende für die Evaluierung 10-fache Kreuzvalidierung

#create 10-fold cross validation scheme
set.seed(6954)
scheme <- evaluationScheme(rrm_reduced, method="cross", k=10, given=20, goodRating=4)

# evaluate with different methods
cv_IBCF <- evaluate(scheme, method="IBCF", type = "topNList",parameter=list(normalize = "Z-score",method="cosine",k=30),n=15)
IBCF run fold/sample [model time/prediction time]
     1  [2.01sec/0.04sec] 
     2  [1.23sec/0.04sec] 
     3  [1.65sec/0.04sec] 
     4  [0.89sec/0.03sec] 
     5  [1.28sec/0.04sec] 
     6  [1.25sec/0.04sec] 
     7  [1sec/0.03sec] 
     8  [1.06sec/0.03sec] 
     9  [1.07sec/0.04sec] 
     10  [1.32sec/0.11sec] 
cv_UBCF <- evaluate(scheme, method="UBCF", type = "topNList",parameter=list(normalize = "Z-score",method="cosine",nn=30),n=15)
UBCF run fold/sample [model time/prediction time]
     1  [0.03sec/0.25sec] 
     2  [0.02sec/0.22sec] 
     3  [0.01sec/0.24sec] 
     4  [0.01sec/0.28sec] 
     5  [0.03sec/0.23sec] 
     6  [0.03sec/0.2sec] 
     7  [0.03sec/0.22sec] 
     8  [0.01sec/0.22sec] 
     9  [0.03sec/0.23sec] 
     10  [0.03sec/0.28sec] 
cv_SVD <- evaluate(scheme, method="SVD", type = "topNList",parameter=list(normalize = "Z-score",k=30),n=15)
SVD run fold/sample [model time/prediction time]
     1  [0.24sec/0.03sec] 
     2  [0.27sec/0.05sec] 
     3  [0.23sec/0.05sec] 
     4  [0.26sec/0.05sec] 
     5  [0.26sec/0.13sec] 
     6  [0.36sec/0.08sec] 
     7  [0.31sec/0.03sec] 
     8  [0.25sec/0.05sec] 
     9  [0.28sec/0.04sec] 
     10  [0.27sec/0.11sec] 
cv_RANDOM <- evaluate(scheme,method="RANDOM",type="topNList",n=15)
RANDOM run fold/sample [model time/prediction time]
     1  [0sec/0.05sec] 
     2  [0sec/0.05sec] 
     3  [0sec/0.05sec] 
     4  [0.01sec/0.03sec] 
     5  [0sec/0.03sec] 
     6  [0sec/0.05sec] 
     7  [0.01sec/0.03sec] 
     8  [0sec/0.03sec] 
     9  [0sec/0.03sec] 
     10  [0sec/0.03sec] 
cv_POP <- evaluate(scheme, method="POPULAR", type = "topNList",parameter=list(normalize = "Z-score"),n=15)
POPULAR run fold/sample [model time/prediction time]
     1  [0.03sec/0.19sec] 
     2  [0.03sec/0.17sec] 
     3  [0.09sec/0.14sec] 
     4  [0.03sec/0.11sec] 
     5  [0.03sec/0.15sec] 
     6  [0.03sec/0.15sec] 
     7  [0.04sec/0.17sec] 
     8  [0.05sec/0.17sec] 
     9  [0.03sec/0.17sec] 
     10  [0.03sec/0.14sec] 
# get the averaged evaluation results
Result_81 <- rbind(avg(cv_IBCF),avg(cv_UBCF),avg(cv_SVD),avg(cv_RANDOM),avg(cv_POP))
rownames(Result_81) <- c("IBCF","UBCF","SVD","RANDOM","POPULAR")
Result_81
            TP      FP      FN       TN   N precision     recall        TPR        FPR  n
IBCF    5.9325  9.0675 78.8625 586.1375 680 0.3955000 0.07568762 0.07568762 0.01501425 15
UBCF    2.0375 12.9625 82.7575 582.2425 680 0.1358333 0.02445926 0.02445926 0.02178287 15
SVD     5.8900  9.1100 78.9050 586.0950 680 0.3926667 0.07739847 0.07739847 0.01513654 15
RANDOM  3.7675 11.2325 81.0275 583.9725 680 0.2511667 0.04431406 0.04431406 0.01871414 15
POPULAR 7.7900  7.2100 77.0050 587.9950 680 0.5193333 0.10232189 0.10232189 0.01184747 15

Higher precision means that an algorithm returns more relevant results than irrelevant ones, and high recall means that an algorithm returns most of the relevant results (whether or not irrelevant ones are also returned).

A perfect precision score of 1.0 means that every result retrieved was relevant (but says nothing about whether all relevant documents were retrieved) whereas a perfect recall score of 1.0 means that all relevant documents were retrieved by the search (but says nothing about how many irrelevant documents were also retrieved)

When I increase the N, the “recall” is getting better (larger value), but the “precision” is getting worse (smaller value).

8.4 Optimiere dein bestes Modell hinsichtlich Hyperparameter. Hinweis: Verwende für den Top-Movie Recommender die Filme mit den höchsten Durchschnittsratings.

# films with only the highest average ratings (ratings > 3)
df_top_avg <- as.data.frame(t(df_reduced))
df_top_avg <- df_top_avg %>% mutate(avg_rating = rowMeans(df_top_avg,na.rm=TRUE,dims=1))%>% arrange(desc(avg_rating))%>% filter(avg_rating>3) %>% select(-avg_rating)
rrm_top_avg <- as(t(df_top_avg),"realRatingMatrix")


set.seed(846954)
scheme_top_avg <- evaluationScheme(rrm_top_avg, method="cross", k=10, given=20, goodRating=4)

# the model Popular has only one parameter: normalize. Here I will compare two normalization methods: z-score and center
POP_top_avg_z <- avg(evaluate(scheme_top_avg, method="POPULAR", type = "topNList",parameter=list(normalize = "Z-score"),n=c(10,15,20,25,30)))
POPULAR run fold/sample [model time/prediction time]
     1  [0.03sec/0.11sec] 
     2  [0.04sec/0.12sec] 
     3  [0.04sec/0.12sec] 
     4  [0.06sec/0.17sec] 
     5  [0.05sec/0.19sec] 
     6  [0.03sec/0.12sec] 
     7  [0.03sec/0.14sec] 
     8  [0.05sec/0.14sec] 
     9  [0.03sec/0.17sec] 
     10  [0.04sec/0.18sec] 
POP_top_avg_center <- avg(evaluate(scheme_top_avg, method="POPULAR", type = "topNList",parameter=list(normalize = "center"),n=c(10,15,20,25,30)))
POPULAR run fold/sample [model time/prediction time]
     1  [0.01sec/0.13sec] 
     2  [0.03sec/0.23sec] 
     3  [0.02sec/0.12sec] 
     4  [0sec/0.14sec] 
     5  [0.02sec/0.12sec] 
     6  [0sec/0.14sec] 
     7  [0.01sec/0.13sec] 
     8  [0.01sec/0.13sec] 
     9  [0.02sec/0.15sec] 
     10  [0.01sec/0.19sec] 
diff_z_center <- cbind((POP_top_avg_z - POP_top_avg_center)[,6:7],POP_top_avg_z[,10]) 
POP_top_avg_z; POP_top_avg_center; diff_z_center
          TP      FP      FN       TN   N precision     recall        TPR         FPR  n
[1,]  5.3750  4.6250 74.2000 461.8000 546 0.5375000 0.07540714 0.07540714 0.009630248 10
[2,]  7.6650  7.3350 71.9100 459.0900 546 0.5110000 0.10625880 0.10625880 0.015300434 15
[3,]  9.5875 10.4125 69.9875 456.0125 546 0.4793750 0.13255558 0.13255558 0.021790133 20
[4,] 11.3750 13.6250 68.2000 452.8000 546 0.4550000 0.15450913 0.15450913 0.028541074 25
[5,] 12.9425 17.0575 66.6325 449.3675 546 0.4314167 0.17375578 0.17375578 0.035781723 30
         TP     FP     FN      TN   N precision     recall        TPR         FPR  n
[1,]  5.380  4.620 74.195 461.805 546 0.5380000 0.07560488 0.07560488 0.009622775 10
[2,]  7.705  7.295 71.870 459.130 546 0.5136667 0.10685028 0.10685028 0.015212167 15
[3,]  9.585 10.415 69.990 456.010 546 0.4792500 0.13201246 0.13201246 0.021785083 20
[4,] 11.390 13.610 68.185 452.815 546 0.4556000 0.15485525 0.15485525 0.028504659 25
[5,] 13.040 16.960 66.535 449.465 546 0.4346667 0.17484967 0.17484967 0.035553745 30
        precision        recall   
[1,] -0.000500000 -0.0001977426 10
[2,] -0.002666667 -0.0005914847 15
[3,]  0.000125000  0.0005431183 20
[4,] -0.000600000 -0.0003461215 25
[5,] -0.003250000 -0.0010938851 30

The cosine similarity matrices by two different methods are equal (with tolerance of 1e-10).

9.4 Vergleiche und diskutiere die Unterschiede deiner mittels Cosine Similarity erzeugten Ähnlichkeitsmatrizen für ordinale und normierte Kundenratings mit der Jaccard-basierten Ähnlichkeitsmatrix.

compare_cos_Jacc <- all.equal(cos_sim_reduced_1,Jacc_sim_reduced,tolerance = 1e-3,check.attributes = FALSE)
compare_cos_Jacc
[1] "Mean relative difference: 2.480877"

The mean relative difference between cosine similarity and jaccard similarity is 2.48.

Jaccard similarity takes only the unique set of items. The cosine similarity takes the total length of the vectors.

10 Implementierung Top-N Metriken

Aufgabe DIY: Implementiere Funktionen für die Beurteilung der Top-N Metriken Precision und Recall sowie für alle Kunden der Item-space Coverage und Novelty und teste diese mit IBCF Recommendations (Basis: reduzierter Datensatz; N = 5, 10, 15, 20, 25, 30)

10.1 Implementiere eine Funktion, um aus Top-N Listen für alle Kunden die Item-space und eines Recommenders zu beurteilen und teste diese.

calc_topn_metrics <- function(mx,split_ratio,N){  # mx: U_I data; split_ratio:train data proportion; n: Top-N
  rrm <- as(mx,"realRatingMatrix")
  # split train, test-known, test_unknown data
  train_test <- evaluationScheme(rrm, method="split", train=split_ratio, k=1, given=20,goodRating=4)
  rrm_train <- getData(train_test,"train")
  rrm_known <- getData(train_test,"known") 
  rrm_unknown <- getData(train_test,"unknown")
  # IBCF model
  model_IBCF <-Recommender(data = rrm_train,method="IBCF",parameter=list(normalize = "Z-score",method="Cosine",k=10))
  # predict Top-N recommendation list
  pred_IBCF <- predict(object = model_IBCF, newdata = rrm_known, n = N,type="topNList")
  
  ####################################
  
  ### accuracy: evaluate the recommendations on "unknown" ratings with metrics precision and recall
  acc_IBCF <- calcPredictionAccuracy(predict(object = model_IBCF, newdata = rrm_known, n = N,type="topNList"),rrm_unknown,given=20,goodRating = 4)
  
  acc_IBCF <- t(as.data.frame(acc_IBCF))
  rownames(acc_IBCF) <- NULL
  
  ####################################
  
  ### item-space coverage: how many percentage of films(from the train data) are in the top-n recommendation lists
  # top n lists for every user
   
  TOP_N_list <- sapply(pred_IBCF@items, function(x) {colnames(as(rrm_known,"matrix"))[x]}) 
  # unique predicted film list of all test users 
  uniq_film_test <- reshape2::melt(as(TOP_N_list,"matrix")) %>% rename(UserID = Var2, rank = Var1, Film_name = value)%>%distinct(Film_name)   # unique film list recommended in test data
  
  # unique film list of the train data
  uniq_film_train <- as.data.frame(t(mx))
  uniq_film_train$cnt <- rowSums(!is.na(uniq_film_train)) # count not NA for each film
  uniq_film_train <- uniq_film_train %>% filter(cnt>0)  # remove the film without any ratings
  
  # calculate the item-space coverage
  coverage <- dim(uniq_film_test)[1] / dim(uniq_film_train)[1] # the coverage
  coverage <- as.data.frame(coverage)
  colnames(coverage) <- "coverage"
  
  ####################################
  
  ### novelty for a given user: ratio of unknown items in the top-n list 
  novelty_table <- data.frame() # an empty dataframe, will be filled with novelty values
  df <- as.data.frame(mx)
  pred_IBCF_all_user <- predict(object = model_IBCF, newdata = rrm, n = N,type="topNList") # predict for all users
  TOP_N_list_all_user <- sapply(pred_IBCF_all_user@items, function(x) {colnames(mx)[x]}) # top-n list for all users
  # df_1: replace the not NA values to the corresponding column name 
  for(i in 1:dim(mx)[1]){
    df_i <- as.data.frame(t(mx))#  
    df_i$Film <- colnames(mx)
    df_i <- df_i[,c(i,(dim(mx)[1]+1))] %>% filter(complete.cases(.)) # list of user-i rated films
    df_i$Film <- rownames(df_i) # add a new column with the same content of rownames
    
    df_top_n <- as.data.frame(TOP_N_list_all_user[,i])   # top-n list of user-i
    colnames(df_top_n) <- "Film"
    
    df_cross <- inner_join(df_i, df_top_n, by="Film")  # inner join the two dataset, we get the rated items in the top-n list
    
    novelty <- 1 - dim(df_cross)[1]/N  # novelty value of user-i
    novelty_table <- rbind(novelty_table, novelty)
  }
  
  novelty_table$UserID <- rownames(mx)
  colnames(novelty_table) <- c("novelty","UserID")
  novelty_table <- novelty_table %>% select(UserID,novelty) # novelty table
  
  ### result of accuracy, coverage, and novelty
  my_list <- list("accuracy" = acc_IBCF,"coverage" = coverage, "novelty" = novelty_table)
  return(my_list) 
}


test <- calc_topn_metrics(mx_reduced,0.8,20)

test$accuracy;test$coverage; test$novelty
      TP      FP     FN       TN   N precision     recall        TPR        FPR
[1,] 6.9 12.9875 77.075 583.0375 680 0.3460227 0.09009878 0.09009878 0.02159826

11 Implementierung Top-N Monitor Aufgabe DIY: Untersuche die relative Übereinstimmung zwischen Top-N Empfehlungen und präferierten Filmen für 4 unterschiedliche Modelle (z.B. IBCF und UBCF mit unterschiedlichen Ähnlichkeits-metriken / Nachbarschaften sowie SVD mit unterschiedlicher Dimensionalitätsreduktion).

11.1 Fixiere 20 zufällig gewählte Testkunden für alle Modellvergleiche,

set.seed(578)
train_test_11 <- evaluationScheme(rrm_reduced, method="split", train=0.95, k=1, given=20,goodRating=4) 

# training dataset has 380 users,test dataset has 20 users 
# given=20: For each test user, 20 films per user will be used for prediction, the rest for evaluation)
rrm_reduced_train_11 <- getData(train_test_11,"train")
rrm_reduced_known_11 <- getData(train_test_11,"known") 
rrm_reduced_unknown_11 <- getData(train_test_11,"unknown")

# ICBF models
model_IBCF_cos_10 <-Recommender(data = rrm_reduced_train_11,method="IBCF",parameter=list(normalize = "Z-score",method="Cosine",k=10))
model_IBCF_cos_50 <-Recommender(data = rrm_reduced_train_11,method="IBCF",parameter=list(normalize = "Z-score",method="Cosine",k=50))

model_IBCF_ps_10 <-Recommender(data = rrm_reduced_train_11,method="IBCF",parameter=list(normalize = "Z-score",method="Pearson",k=10))
model_IBCF_ps_50 <-Recommender(data = rrm_reduced_train_11,method="IBCF",parameter=list(normalize = "Z-score",method="Pearson",k=50))

# UBCF models
model_UBCF_cos_10 <-Recommender(data = rrm_reduced_train_11,method="UBCF",parameter=list(normalize = "Z-score",method="Cosine",nn=10))
model_UBCF_cos_50 <-Recommender(data = rrm_reduced_train_11,method="UBCF",parameter=list(normalize = "Z-score",method="Cosine",nn=50))

model_UBCF_ps_10 <-Recommender(data = rrm_reduced_train_11,method="UBCF",parameter=list(normalize = "Z-score",method="Pearson",nn=10))
model_UBCF_ps_50 <-Recommender(data = rrm_reduced_train_11,method="UBCF",parameter=list(normalize = "Z-score",method="Pearson",nn=50))

# SVD models
model_SVD_10 <- Recommender(data = rrm_reduced_train_11,method="SVD",parameter=list(normalize = "Z-score",k=10))
model_SVD_50 <- Recommender(data = rrm_reduced_train_11,method="SVD",parameter=list(normalize = "Z-score",k=50))

# evaluation of the predictions
acc_IBCF_cos_10 <- calcPredictionAccuracy(predict(object = model_IBCF_cos_10, newdata = rrm_reduced_known_11, n = 15,type="topNList"),rrm_reduced_unknown_11,given=20,goodRating = 4)
acc_IBCF_cos_50 <- calcPredictionAccuracy(predict(object = model_IBCF_cos_50, newdata = rrm_reduced_known_11, n = 15,type="topNList"),rrm_reduced_unknown_11,given=20,goodRating = 4)
acc_IBCF_ps_10 <- calcPredictionAccuracy(predict(object = model_IBCF_ps_10, newdata = rrm_reduced_known_11, n = 15,type="topNList"),rrm_reduced_unknown_11,given=20,goodRating = 4)
acc_IBCF_ps_50 <- calcPredictionAccuracy(predict(object = model_IBCF_ps_50, newdata = rrm_reduced_known_11, n = 15,type="topNList"),rrm_reduced_unknown_11,given=20,goodRating = 4)

acc_UBCF_cos_10 <- calcPredictionAccuracy(predict(object = model_UBCF_cos_10, newdata = rrm_reduced_known_11, n = 15,type="topNList"),rrm_reduced_unknown_11,given=20,goodRating = 4)
acc_UBCF_cos_50 <- calcPredictionAccuracy(predict(object = model_UBCF_cos_50, newdata = rrm_reduced_known_11, n = 15,type="topNList"),rrm_reduced_unknown_11,given=20,goodRating = 4)
acc_UBCF_ps_10 <- calcPredictionAccuracy(predict(object = model_UBCF_ps_10, newdata = rrm_reduced_known_11, n = 15,type="topNList"),rrm_reduced_unknown_11,given=20,goodRating = 4)
acc_UBCF_ps_50 <- calcPredictionAccuracy(predict(object = model_UBCF_ps_50, newdata = rrm_reduced_known_11, n = 15,type="topNList"),rrm_reduced_unknown_11,given=20,goodRating = 4)

acc_SVD_10 <- calcPredictionAccuracy(predict(object = model_SVD_10, newdata = rrm_reduced_known_11, n = 15,type="topNList"),rrm_reduced_unknown_11,given=20,goodRating = 4)
acc_SVD_50 <- calcPredictionAccuracy(predict(object = model_SVD_50, newdata = rrm_reduced_known_11, n = 15,type="topNList"),rrm_reduced_unknown_11,given=20,goodRating = 4)

acc_table <- rbind(acc_IBCF_cos_10,acc_IBCF_cos_50,acc_IBCF_ps_10,acc_IBCF_ps_50,acc_UBCF_cos_10,acc_UBCF_cos_50,acc_UBCF_ps_10,acc_UBCF_ps_50,acc_SVD_10,acc_SVD_50)

acc_table
                  TP    FP    FN     TN   N precision     recall        TPR        FPR
acc_IBCF_cos_10 6.30  8.70 87.15 577.85 680 0.4200000 0.07252980 0.07252980 0.01456784
acc_IBCF_cos_50 6.75  8.25 86.70 578.30 680 0.4500000 0.07716093 0.07716093 0.01370982
acc_IBCF_ps_10  3.10 11.15 90.35 575.40 680 0.2364881 0.03374307 0.03374307 0.01900455
acc_IBCF_ps_50  5.15  9.85 88.30 576.70 680 0.3433333 0.05386252 0.05386252 0.01642536
acc_UBCF_cos_10 2.85 12.15 90.60 574.40 680 0.1900000 0.03506794 0.03506794 0.02069613
acc_UBCF_cos_50 2.45 12.55 91.00 574.00 680 0.1633333 0.03580625 0.03580625 0.02140033
acc_UBCF_ps_10  2.30 12.70 91.15 573.85 680 0.1533333 0.02657352 0.02657352 0.02167117
acc_UBCF_ps_50  2.45 12.55 91.00 574.00 680 0.1633333 0.03007206 0.03007206 0.02136549
acc_SVD_10      6.95  8.05 86.50 578.50 680 0.4633333 0.07790237 0.07790237 0.01341930
acc_SVD_50      5.90  9.10 87.55 577.45 680 0.3933333 0.07229660 0.07229660 0.01537873

In the IBCF model, both precision and recall are better with cosine method and 50 neighbors.

In the UBCF model, cosine method and 10 neighbors is a better combination.

In the SVD model, precision and recall are better with singular value of 10.

Through all the models, The SVD model with singular value of 10 has the best precision (0.463) and recall (0.0779).

11.2 Bestimme den Anteil der Top-N Empfehlung nach Genres pro Kunde,

Top_n_genre <- function(Top_n_list,n){   # mx is user-item matrix; Top_n_list: top-n matrix; n: the "n" in top-n 
  
  table = data.frame()
  for(i in 1:dim(Top_n_list)[2]){
    df_top <- as.data.frame(Top_n_list[,i])
    colnames(df_top) <- "Film"
    
    df_film_genre_1 <- as.data.frame(mx_film_genre)
    df_film_genre_1$Film <- rownames(df_film_genre_1)
    
    df_top <- left_join(df_top,df_film_genre_1,by=("Film")) %>% select(-Film)
    df_top <- df_top[-1,] 
    total <- sum(df_top)
    df_top["ratio",] <- colSums(df_top)/total
    df_top <- df_top["ratio",]

    table <- rbind(table,df_top)
  }
  rownames(table) <- colnames(Top_n_list)
  return(table)
}


# Top-15 recommendation list of SVD with k = 10
Pred_SVD_k10 <- predict(object = model_SVD_10, newdata = rrm_reduced_known_11, n = 15,type=c("topNList"))
Top15_SVD <- sapply(Pred_SVD_k10@items, function(x) {colnames(df_reduced)[x]})

Top_15_recommendations <- Top_n_genre(Top15_SVD,15) # the percentage of top-15 recommendations by genre per test user

Top_15_recommendations;summary(rowSums(Top_15_recommendations))[-4] # check if the total genre ratio for each user = 1
   Min. 1st Qu.  Median 3rd Qu.    Max. 
      1       1       1       1       1 

The table shows the percentage of genres in the top-15 recommendation list per user.

The sum of each row are all 1, this indicates the total ratio of each user are all correct.

11.3 Bestimme pro Kunde den Anteil nach Genres seiner Top-Filme (=Filme, welche vom Kunden die besten Bewertungen erhalten haben)

Top_film_genre <- function(mx,n){   # mx is user-item matrix, n: top-n rated films
  
  table = data.frame()
  for(i in 1:dim(mx)[1]){
    df_top <- as.data.frame(t(mx))
    df_top$Film <- rownames(df_top)
    df_top <- df_top[,c(i,(dim(mx)[1]+1))]
    colnames(df_top) <- c("Ratings","Film")
    df_top <- df_top %>% filter(complete.cases(.)) %>% arrange(desc(Ratings)) %>% slice(1:n)
    
    df_film_genre_1 <- as.data.frame(mx_film_genre)
    df_film_genre_1$Film <- rownames(df_film_genre_1)
    
    df_left_join <- left_join(df_top,df_film_genre_1,by=("Film"))
    
    df_top <- df_left_join[,-(1:2)] 
    total <- sum(df_top)
    df_top["ratio",] <- colSums(df_top)/total
    df_top <- df_top["ratio",]
    table <- rbind(table,df_top)
  }
  rownames(table) <- rownames(mx)
  return(table)
}

Top_15_films <- Top_film_genre(mx_reduced,15) # genres proportion of the top 15 films for every user
Top_15_films
summary(rowSums(Top_15_films))[-4]
   Min. 1st Qu.  Median 3rd Qu.    Max. 
      1       1       1       1       1 

The first table shows the percentage of genres in the top-15 rated list per user.

The sum of each row are all 1, this indicates the total ratio of each user are all correct.

11.4 Vergleiche pro Kunde Top-Empfehlungen und Top-Filmen nach Genres,

# filter the Top-Filmen with the users only appear in the Top-recommendation
Top_15_films_reduced <- Top_15_films
Top_15_films_reduced$UserID <- rownames(Top_15_films_reduced)
Top_15_films_reduced <- Top_15_films_reduced %>% filter(UserID %in% rownames(Top_15_recommendations)) %>% select(-UserID) # with 20 users

# calculate the mean absolute error
MAE_top_genre <- rowSums(abs(Top_15_films_reduced - Top_15_recommendations))/20
"MAE between Top-recommendations and Top-films by genres per user:"; MAE_top_genre;"the five number statistics of the MAE:";summary(MAE_top_genre)[-4]
[1] "MAE between Top-recommendations and Top-films by genres per user:"
       393        417        279        474        472        379        823        267        577        536 
0.03677885 0.02048067 0.02954545 0.04768892 0.02958937 0.02647059 0.02817204 0.03555556 0.03646552 0.04252252 
       899        484        361        391        901        215        323        918        828        552 
0.03333333 0.02379032 0.04028122 0.03775388 0.02978177 0.04346591 0.03600000 0.03081897 0.04404894 0.02547093 
[1] "the five number statistics of the MAE:"
      Min.    1st Qu.     Median    3rd Qu.       Max. 
0.02048067 0.02920210 0.03444444 0.03838572 0.04768892 
"MSE between Top-recommendations and Top-films by genres per user:"
[1] "MSE between Top-recommendations and Top-films by genres per user:"
MSE_top_genre <- rowSums((Top_15_films_reduced - Top_15_recommendations)^2)/20
MSE_top_genre;"the five number statistics of the MSE:";summary(MSE_top_genre)[-4]
        393         417         279         474         472         379         823         267         577         536 
0.003692125 0.001040455 0.002926997 0.006015010 0.002028927 0.002454184 0.001581634 0.002370370 0.002941290 0.004354336 
        899         484         361         391         901         215         323         918         828         552 
0.002295684 0.001557035 0.004265842 0.003357985 0.002117153 0.003690761 0.003457500 0.002399952 0.006203655 0.001318853 
[1] "the five number statistics of the MSE:"
       Min.     1st Qu.      Median     3rd Qu.        Max. 
0.001040455 0.002095096 0.002690591 0.003691102 0.006203655 
"RMSE between Top-recommendations and Top-films by genres per user:"
[1] "RMSE between Top-recommendations and Top-films by genres per user:"
RMSE_top_genre <- sqrt(rowSums((Top_15_films_reduced - Top_15_recommendations)^2)/20)
RMSE_top_genre;"the five number statistics of the RMSE:";summary(RMSE_top_genre)[-4]
       393        417        279        474        472        379        823        267        577        536 
0.06076286 0.03225609 0.05410173 0.07755650 0.04504361 0.04953972 0.03976977 0.04868645 0.05423366 0.06598740 
       899        484        361        391        901        215        323        918        828        552 
0.04791330 0.03945928 0.06531341 0.05794812 0.04601253 0.06075163 0.05880051 0.04898930 0.07876328 0.03631601 
[1] "the five number statistics of the RMSE:"
      Min.    1st Qu.     Median    3rd Qu.       Max. 
0.03225609 0.04577030 0.05182073 0.06075444 0.07876328 

Three quantitativ metrics MAE(mean average error), MSE(mean squared error), RMSE(the root mean squared error) were used to compare the difference between the top-recommendations and top-rated-films by genres.

11.5 Definiere eine Qualitätsmetrik für Top-N Listen und teste sie.

# MAP: Average Precision and Mean Average Precision

MAP <- function(mx,Top_n_list,n){
  # extract the users in the Top-n lists, or use direct the test dataset.
  mx_part <- as.data.frame(mx) %>% filter(rownames(as.data.frame(mx)) %in% colnames(as.data.frame(Top_n_list)))# user_film
  mx_part <- as.data.frame(t(mx_part)) # transpose mx_part_users to film_user
  mx_part$Film <- rownames(mx_part) # generate new column "Film" same as the rownames
  Top_n_list <- as.data.frame(Top_n_list)
  Top_n_list$Rank <- 1:n # generate new column "Rank" to represent the ranks of the recommended films
  
  summe_precision <- 0
  for(i in (dim(mx_part)[2]-1)){
    Top_i <- Top_n_list[,c(all_of(i),dim(Top_n_list)[2])] # extract the top_n_list and rank of the i-th user
    colnames(Top_i) <- c("Film","Rank") # rename the columns as "Film" and "Rank"
    mx_i <- mx_part %>% select(c(all_of(i),dim(mx_part)[2]))       # mx_i: extract the ratings and Film names of i-th user from rating matrix
    colnames(mx_i) <- c("Rating","Film")
    mx_join <- left_join(Top_i,mx_i,by="Film") %>% filter(Rating>3) # left_join the ratings to the Top-n list by "Film". mx_1 has the columns of "Film", "Rank", and ratings; filter the relevant items (ratings greater than 3); 
    mx_join <- mx_join %>% mutate(Numerator = 1:dim(mx_join)[1],Precision = Numerator/Rank) # generate new column "Numerator" which is a new rank only for the relevant items, and new column "Precision" which is the Precision of every relevant items.

    avg_user_i_precision <- mean(mx_join$Precision)  # average precision of user-i
    summe_precision <- summe_precision + avg_user_i_precision
  }
  map <- summe_precision/(dim(Top_n_list)[2]-1) # mean average precision
  return(map)
}

MAP(mx_reduced,TOP15_IBCF,15)
[1] 0.008875812

firstly, for one user, find out the rank of the m-th relevant item (rating > 3) in the top_n_list, then calculate the precision: m/n.

secondly, calculate the precisions of all relevant items.

the average precision of one user: average all the precision of relevant items.

MAP: average precision of all users.

LS0tDQp0aXRsZTogIkNvbGxhYm9yYXRpdmUgTW92aWUgUmVjb21tZW5kZXIiDQpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sNCmVkaXRvcl9vcHRpb25zOiANCiAgbWFya2Rvd246IA0KICAgIHdyYXA6IDcyDQotLS0NCg0KMS4gIExpYnJhcnkgdW5kIERhdGENCg0KYGBge3J9DQpsaWJyYXJ5KHRpZHl2ZXJzZSkNCmxpYnJhcnkoZHBseXIpDQpsaWJyYXJ5KGRhdGEudGFibGUpDQpsaWJyYXJ5KGdncGxvdDIpDQpsaWJyYXJ5KHJlc2hhcGUyKQ0KbGlicmFyeShyc2FtcGxlKQ0KbGlicmFyeShyZWNvbW1lbmRlcmxhYikNCmRhdGEoTW92aWVMZW5zZSkNCmBgYA0KDQoyLiAgRXhwbG9yYXRpdmUgRGF0ZW5hbmFseXNlDQoNCmBgYHtyfQ0KbXhfdXNlcl9maWxtIDwtIGFzKE1vdmllTGVuc2UsICJtYXRyaXgiKSAgIyBjb252ZXJ0IHJlYWxyYXRpbmdtYXRyaXggdG8gbm9ybWFsIG1hdHJpeA0KZGZfdXNlcl9maWxtIDwtIGFzLmRhdGEuZnJhbWUobXhfdXNlcl9maWxtKSAgICMgIGNvbnZlcnQgbWF0cml4IHRvIGRhdGFmcmFtZSBmb3JtDQpkZl9maWxtX3VzZXIgPC0gYXMuZGF0YS5mcmFtZSh0KG14X3VzZXJfZmlsbSkpICMgdHJhbnNwb3NlIHRoZSBkYXRhZnJhbWU6IGVhY2ggcm93IGlzIGEgbW92aWUgbmFtZSwgZWFjaCBjb2x1bW4gaXMgYSB1c2VyDQpgYGANCg0KMi4xIFdlbGNoZXMgc2luZCBkaWUgYW0gaMOkdWZpZ3N0ZW4gZ2VzY2hhdXRlbiBHZW5yZXMvRmlsbWU/DQoNCmBgYHtyfQ0KZGZfMjEgPC0gZGZfZmlsbV91c2VyICU+JSBtdXRhdGUoY250ID0gcm93U3VtcyghaXMubmEoZGZfZmlsbV91c2VyKSkpICU+JSBhcnJhbmdlKGRlc2MoY250KSkgJT4lIGZpbHRlcihjbnQgPT0gbWF4KGNudCkpICU+JSBzZWxlY3QoJ2NudCcpDQpkZl8yMQ0KYGBgDQojIyMgRGllIGFtIGjDpHVmaWdzdGVuIGdlc2NoYXV0ZW4gRmlsbWUgaXN0IFN0YXIgV2Fycy4NCg0KMi4yIFdpZSB2ZXJ0ZWlsZW4gc2ljaCBkaWUgS3VuZGVucmF0aW5ncyBnZXNhbXRoYWZ0IHVuZCBuYWNoIEdlbnJlcz8NCg0KYGBge3J9DQpkZl91bmxpc3QgPC0gZGF0YS5mcmFtZShyYXRpbmc9dW5saXN0KGRmX2ZpbG1fdXNlcikpICAgICAgICAgICAgIyB1bmxpc3QgdGhlIGRhdGFmcmFtZQ0KZ2dwbG90KGRmX3VubGlzdCxhZXMocmF0aW5nKSkgKyBnZW9tX2hpc3RvZ3JhbSgpICsgICAgICAgICAgICAgICAgIyBkaWUgVmVydGVpbHVuZyBkZXIgS3VuZGVucmF0aW5ncyBnZXNhbXRoYWZ0DQogIGxhYnMoeD0iUmF0aW5ncyIsIHk9IkNvdW50Iix0aXRsZT0iRGlzdHJpYnV0aW9uIG9mIHRoZSB1c2VyIHJhdGluZ3MiKSArDQogIHRoZW1lKHBsb3QudGl0bGUgPSBlbGVtZW50X3RleHQoaGp1c3QgPSAwLjUpKQ0KYGBgDQojIyMgVGhlIGFib3ZlIGhpc3RvZ3JhbSBvZiByYXRpbmdzIGRpc3RyaWJ1dGlvbiBpcyBsZWZ0IHNrZXdlZCwgd2l0aCB0aGUgbW9kZSA9IDQuDQoNCg0KYGBge3J9DQpteF9maWxtX2dlbnJlIDwtIGFzLmRhdGEuZnJhbWUoTW92aWVMZW5zZU1ldGEpIA0Kcm93bmFtZXMobXhfZmlsbV9nZW5yZSkgPC0gbXhfZmlsbV9nZW5yZSR0aXRsZQ0KbXhfZmlsbV9nZW5yZSA8LSBhcy5tYXRyaXgobXhfZmlsbV9nZW5yZVssNToyMl0pICAgIyBNb3ZpZSBHZW5yZSBNYXRyaXgNCg0KbXhfdXNlcl9maWxtW2lzLm5hKG14X3VzZXJfZmlsbSldIDwtIDANCg0KbXhfdXNlcl9nZW5yZSA8LSBteF91c2VyX2ZpbG0gJSolIG14X2ZpbG1fZ2VucmUNCg0KbXhfZ2VucmVfdXNlciA8LSBhcy5kYXRhLmZyYW1lKHQobXhfdXNlcl9nZW5yZSkpICAgICMgYTogU3TDpHJrZSBHZW5yZSBLb21iaW5hdGlvbiB2b2xsc3TDpG5kaWcNCm14X2dlbnJlX3VzZXIkc3VtbWUgPC0gcm93U3VtcyhteF9nZW5yZV91c2VyKSAgICAgICAgICAgICAgICMgbmV3IGNvbHVtbiAic3VtbWUiOiBzdW1tZSB1c2VyIHJhdGluZ3Mgb2YgZWFjaCBnZW5yZQ0KbXhfZ2VucmVfdXNlciA8LSBjYmluZChnZW5yZSA9IHJvd25hbWVzKG14X2dlbnJlX3VzZXIpLCBteF9nZW5yZV91c2VyKSMgbmV3IGNvbHVtbiAiZ2VucmUiOiBnZW5yZSBuYW1lIGNvcGllZCBmcm9tIHJvd25hbWVzDQpnZ3Bsb3QobXhfZ2VucmVfdXNlcixhZXMoc3VtbWUsZ2VucmUpKSArIGdlb21fY29sKCkgKyBsYWJzKHg9ICJzdW1tZWQgcmF0aW5ncyBvZiBhbGwgdXNlcnMiLCB5PSJHZW5yZSIsdGl0bGU9IkRpc3RyaWJ1dGlvbiBvZiB0aGUgdXNlciByYXRpbmdzIGJ5IGdlbnJlIGNvbWJpbmF0aW9uIikgKyANCiAgdGhlbWUocGxvdC50aXRsZSA9IGVsZW1lbnRfdGV4dChoanVzdCA9IDAuNSkpDQpteF9nZW5yZV91c2VyIDwtIG14X2dlbnJlX3VzZXIgJT4lIHNlbGVjdCgtZ2VucmUpDQpgYGANCiMjIyBBYm92ZSBpcyB0aGUgZGlzdHJpYnV0aW9uIG9mIHJhdGluZ3MgYnkgZ2VucmUsICJkcmFtYSIgaGFzIHRoZSBoaWdoZXN0IHN1bW1lZCByYXRpbmdzLg0KDQpgYGB7cn0NCmRmXzIyIDwtIGFzLmRhdGEuZnJhbWUodChteF9maWxtX2dlbnJlKSkgJT4lIG11dGF0ZShjbnQgPSByb3dTdW1zKGFzLmRhdGEuZnJhbWUodChteF9maWxtX2dlbnJlKSkpKSU+JSBhcnJhbmdlKGRlc2MoY250KSkgICMgYWRkIG5ldyBjb2x1bW46IGNvdW50IGZvciBlYWNoIGdlbnJlcw0KZGZfMjIgPC0gY2JpbmQoZ2VucmVzID0gcm93bmFtZXMoZGZfMjIpLGRmXzIyKSAgICAgICAgICAgICAgICMgaW5kZXggYXMgYSBjb2x1bW4NCnJvd25hbWVzKGRmXzIyKSA8LSAxOm5yb3coZGZfMjIpICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgZ2VuZXJhdGUgbmV3IGluZGV4DQoNCmdncGxvdChkZl8yMixhZXMoeCA9IChyZW9yZGVyKGdlbnJlcyxjbnQpKSwgeSA9IGNudCkpICsgZ2VvbV9jb2woKSArIGNvb3JkX2ZsaXAoKSArDQogIGxhYnMoeT0iTnVtYmVyIG9mIFZpZXdzIiwgeD0iR2VucmVzIix0aXRsZT0iRGlzdHJpYnV0aW9uIGJ5IGdlbnJlcyIpICsgDQogIHRoZW1lKHBsb3QudGl0bGUgPSBlbGVtZW50X3RleHQoaGp1c3QgPSAwLjUpKQ0KYGBgDQojIyMgVGhlIHBsb3QgYWJvdmUgc2hvd3MgdGhlIGRpc3RyaWJ1dGlvbiBvZiB2aWV3cyBieSBnZW5yZS4gVGhlIGdlbnJlIGRyYW1hIGhhcyB0aGUgaGlnaGVzdCBudW1iZXIgb2Ygdmlld3MuDQoNCjIuMyBXaWUgdmVydGVpbGVuIHNpY2ggZGllIG1pdHRsZXJlbiBLdW5kZW5yYXRpbmdzIHBybyBGaWxtPw0KDQpgYGB7cn0NCmRmX2F2Z19yYXRpbmdfZmlsbSA8LSBkZl9maWxtX3VzZXIgJT4lIG11dGF0ZShhdmdfcmF0aW5nID0gcm93TWVhbnMoZGZfZmlsbV91c2VyLG5hLnJtID0gVFJVRSwgZGltcyA9IDEpKSAlPiUgc2VsZWN0KCdhdmdfcmF0aW5nJykNCmdncGxvdChkZl9hdmdfcmF0aW5nX2ZpbG0sYWVzKGF2Z19yYXRpbmcpKSArIGdlb21faGlzdG9ncmFtKGJpbndpZHRoID0gMSkgKyAgICAgICAgICAgICAgICAjIGRpZSBWZXJ0ZWlsdW5nDQogIGxhYnMoeD0iTWVhbiB1c2VyLXJhdGluZ3MgcGVyIGZpbG0iLCB5PSJDb3VudCBvZiBmaWxtcyIsdGl0bGU9IkRpc3RyaWJ1dGlvbiBvZiB0aGUgbWVhbiB1c2VyLXJhdGluZ3MgcGVyIGZpbG0iKSArIA0KICB0aGVtZShwbG90LnRpdGxlID0gZWxlbWVudF90ZXh0KGhqdXN0ID0gMC41KSkNCg0KYGBgDQojIyMgVGhlIHBsb3Qgc2hvd2VkIHVzIHRoYXQgdGhlIG1vZGUgb2YgYXZlcmFnZSByYXRpbmdzIHBlciBmaWxtIGlzIDMuIE1vc3Qgb2YgbW92aWVzIGhhdmUgdGhlIGF2ZXJhZ2UgcmF0aW5nIGxhcmdlciB0aGFuIDIuIA0KDQoNCjIuNCBXaWUgc3Rhcmsgc3RyZXVlbiBkaWUgUmF0aW5ncyB2b24gaW5kaXZpZHVlbGxlbiBLdW5kZW4/DQoNCmBgYHtyfQ0KZGZfYXZnX3JhdGluZ191c2VyIDwtIGRmX3VzZXJfZmlsbSAlPiUgbXV0YXRlKGF2Z19yYXRpbmcgPSByb3dNZWFucyhkZl91c2VyX2ZpbG0sbmEucm0gPSBUUlVFLCBkaW1zID0gMSkpICU+JSBzZWxlY3QoJ2F2Z19yYXRpbmcnKQ0KZ2dwbG90KGRmX2F2Z19yYXRpbmdfdXNlcixhZXMoYXZnX3JhdGluZykpICsgZ2VvbV9oaXN0b2dyYW0oYmlucyA9IDUpICsgICAgICAgICAgICAgICAgIyBkaWUgVmVydGVpbHVuZw0KICBsYWJzKHg9Ik1lYW4gdXNlci1yYXRpbmdzIHBlciB1c2VyIiwgeT0iQ291bnQgb2YgdXNlcnMiLHRpdGxlPSJEaXN0cmlidXRpb24gb2YgdGhlIG1lYW4gdXNlci1yYXRpbmdzIHBlciB1c2VyIikrIA0KICB0aGVtZShwbG90LnRpdGxlID0gZWxlbWVudF90ZXh0KGhqdXN0ID0gMC41KSkNCmBgYA0KIyMjIFRoZSBwbG90IHNob3dzIHRoZSBtb2RlIG9mIGF2ZXJhZ2UgdXNlciByYXRpbmdzIHBlciB1c2VyIGlzIDMuIE1vc3Qgb2YgdGhlIGF2ZXJhZ2UgcmF0aW5ncyBhcmUgMyBvciA0Lg0KDQoNCjIuNSBXZWxjaGVuIEVpbmZsdXNzIGhhdCBkaWUgTm9ybWllcnVuZyBkZXIgUmF0aW5ncyBwcm8gS3VuZGUgYXVmIGRlcmVuIFZlcnRlaWx1bmc/DQpgYGB7cn0NCmRmX2F2Z19yYXRpbmdfdXNlciA8LSBkZl91c2VyX2ZpbG0gJT4lIG11dGF0ZShhdmdfcmF0aW5nID0gcm93TWVhbnMoZGZfdXNlcl9maWxtLG5hLnJtID0gVFJVRSwgZGltcyA9IDEpKSAlPiUgc2VsZWN0KCdhdmdfcmF0aW5nJykNCmdncGxvdChkZl9hdmdfcmF0aW5nX3VzZXIsYWVzKGF2Z19yYXRpbmcpKSArIGdlb21faGlzdG9ncmFtKGJpbnMgPSAyMCkgKyAgICAgICAgICAgICAgICAjIGRpZSBWZXJ0ZWlsdW5nDQogIGxhYnMoeD0iTWVhbiByYXRpbmdzIHBlciB1c2VyIiwgeT0iQ291bnQgb2YgdXNlcnMiLHRpdGxlPSJEaXN0cmlidXRpb24gb2YgdGhlIG1lYW4gcmF0aW5ncyBwZXIgdXNlciIpKyANCiAgdGhlbWUocGxvdC50aXRsZSA9IGVsZW1lbnRfdGV4dChoanVzdCA9IDAuNSkpDQpgYGANCg0KYGBge3J9DQpub3JtYWxpemVkX21vdmllbGVucyA8LSBhcyhub3JtYWxpemUoTW92aWVMZW5zZSxtZXRob2QgPSAiei1zY29yZSIpLCAibWF0cml4IikNCm5vcm1hbGl6ZWRfbW92aWVsZW5zIDwtIGFzLmRhdGEuZnJhbWUobm9ybWFsaXplZF9tb3ZpZWxlbnMpDQpub3JtYWxpemVkX2F2Z19yYXRpbmdfdXNlciA8LSBub3JtYWxpemVkX21vdmllbGVucyAlPiUgbXV0YXRlKGF2Z19yYXRpbmc9cm93TWVhbnMobm9ybWFsaXplZF9tb3ZpZWxlbnMsbmEucm09VFJVRSwgZGltcz0xKSkgJT4lIHNlbGVjdCgnYXZnX3JhdGluZycpICANCg0KZ2dwbG90KG5vcm1hbGl6ZWRfYXZnX3JhdGluZ191c2VyLGFlcyhhdmdfcmF0aW5nKSkgKyBnZW9tX2hpc3RvZ3JhbShiaW5zID0gMjApICsgICAgICAgICAgICAgICAgIyBkaWUgVmVydGVpbHVuZw0KICBsYWJzKHg9Ik1lYW4gbm9ybWFsaXplZCByYXRpbmdzIHBlciB1c2VyIiwgeT0iQ291bnQgb2YgdXNlcnMiLHRpdGxlPSJEaXN0cmlidXRpb24gb2YgdGhlIG1lYW4gbm9ybWFsaXplZCByYXRpbmdzIHBlciB1c2VyIikgKyANCiAgdGhlbWUocGxvdC50aXRsZSA9IGVsZW1lbnRfdGV4dChoanVzdCA9IDAuNSkpDQpgYGANCiMjIyB3aXRob3V0IG5vcm1hbGl6YXRpb24gKGZpcnN0IHBsb3QpOiB0aGUgYXZlcmFnZSByYXRpbmdzIGFyZSBzbGlnaHRseSBsZWZ0IHNrZXdlZCwgd2l0aCB0aGUgbW9kZSBvZiAzLjguIFRoZSByYXRpbmdzIHZhcnkgYSBsb3QgYWNyb3NzIGRpZmZlcmVudCB1c2Vycy4NCg0KIyMjIHdpdGggWi1zY29yZSBub3JtYWxpemF0aW9uIChzZWNvbmQgcGxvdCk6IHRoZSBhdmVyYWdlIHJhdGluZ3MgcGVyIHVzZXIgYXJlIGFsbCBhcm91bmQgMC4gVGhpcyBtZWFuLCB0aGUgcmF0aW5ncyBmcm9tIGRpZmZlcmVudCB1c2VycyBhcmUgbm9ybWFsaXplZCB0byB0aGUgc2FtZSBzY2FsZSwgd2l0aCB0aGUgbWVhbiBvZiAwLCB0aGUgc3RhbmRhcmQgZGV2aWF0aW9uIG9mIDEuIFRoaXMgd2lsbCByZWR1Y2UgdGhlIGluZmx1ZW5jZSBvZiByYXRpbmcgaGFiaXRzIG9mIGRpZmZlcmVudCB1c2Vycy4gDQoNCjIuNiBXZWxjaGUgc3RydWt0dXJlbGxlbiBDaGFyYWt0ZXJpc3Rpa2EgKHouQi4gU3BhcnNpdHkpIHVuZCBBdWZmw6RsbGlna2VpdGVuIHplaWd0IGRpZSBVc2VyLUl0ZW0gTWF0cml4Pw0KDQojIyMgUmVjb21tZW5kZXIgU3lzdGVtIGRhdGEgdXN1YWxseSBjb250YWlucyBhIGxhcmdlIG51bWJlcnMgb2YgdXNlcnMocm93cykgYW5kIGl0ZW1zIChjb2x1bW5zKSwgYnV0IGEgc2luZ2xlIHVzZXIgaW50ZXJhY3RzIHdpdGggb25seSBhIHNtYWxsIHN1YnNldCBvZiB0aGUgaXRlbXMuIFRoaXMgbWVhbnMsIHRoZSBkYXRhZnJhbWUgY29uc2lzdHMgb2YgbWFueSB6ZXJvIHZhbHVlcywgdGhlIHN0cnVjdHVyZSBpcyBleHRyZW1lbHkgc3BhcnNlLg0KDQojIyMgVGhlIFVzZXItSXRlbSBNYXRyaXggb2YgTW92aWVMZW5zZSBkYXRhc2V0IGlzIGRnQ01hdHJpeCwgd2hpY2ggaXMgYSBjbGFzcyBvZiBzcGFyc2UgbnVtZXJpYyBtYXRyaWNlcyBpbiB0aGUgY29tcHJlc3NlZCwgc3BhcnNlLCBjb2x1bW4tb3JpZW50ZWQgZm9ybWF0LiBJbiB0aGlzIGltcGxlbWVudGF0aW9uIHRoZSBub24temVybyBlbGVtZW50cyBpbiB0aGUgY29sdW1ucyBhcmUgc29ydGVkIGludG8gaW5jcmVhc2luZyByb3cgb3JkZXIuDQoNCg0KMyBEYXRlbnJlZHVrdGlvbg0KDQozLjEgUmVkdXppZXJlIGRlbiBNb3ZpZUxlbnNlIERhdGVuc2F0eiBhdWYgcnVuZCA0MDAgS3VuZGVuIHVuZCA3MDAgRmlsbWUsIGluZGVtIGR1IEZpbG1lIHVuZCBLdW5kZW4gbWl0IHNlaHIgd2VuaWdlbiBSYXRpbmdzIGVudGZlcm5zdC4NCg0KYGBge3J9DQpkZl9yZWR1Y2VkIDwtIGRmX2ZpbG1fdXNlciAlPiUgbXV0YXRlKG5fcHJvX2ZpbG0gPSByb3dTdW1zKCFpcy5uYShkZl9maWxtX3VzZXIpKSkgJT4lIGFycmFuZ2UoZGVzYyhuX3Byb19maWxtKSkgJT4lIHNsaWNlKDA6NzAwKSU+JSBzZWxlY3QoLW5fcHJvX2ZpbG0pICAgICAgICMgcmVkdWNlIHRvIDcwMCBtb3ZpZXMNCmRmX3JlZHVjZWQgPC0gYXMuZGF0YS5mcmFtZSh0KGRmX3JlZHVjZWQpKSANCmRmX3JlZHVjZWQgPC0gZGZfcmVkdWNlZCAlPiUgbXV0YXRlKG5fcHJvX3VzZXIgPSByb3dTdW1zKCFpcy5uYShkZl9yZWR1Y2VkKSkpICU+JSBhcnJhbmdlKGRlc2Mobl9wcm9fdXNlcikpICU+JSBzbGljZSgwOjQwMCkgJT4lIHNlbGVjdCgtbl9wcm9fdXNlcikgICMgcmVkdWNlIHRvIDQwMCB1c2Vycw0KZGZfcmVkdWNlZCAgICMgd2l0aCA0MDAgdXNlcnMgYW5kIDcwMCBmaWxtcy4NCmBgYA0KDQozLjIgVW50ZXJzdWNoZSB1bmQgZG9rdW1lbnRpZXJlIGRpZSBFaWdlbnNjaGFmdGVuIGRlcyByZWR1emllcnRlbiBEYXRlbnNhdHplcyB1bmQgYmVzY2hyZWliZSBkZW4gRWZmZWt0IGRlciBEYXRlbnJlZHVrdGlvbjogQW56YWhsIEZpbG1lIHVuZCBLdW5kZW4gc293aWUgU3BhcnNpdHkgdm9yIHVuZCBuYWNoIERhdGVucmVkdWt0aW9uDQoNCiMjIyBWb3IgRGF0ZW5yZWR1a3Rpb246IDE2NjQgTW92aWVzLCA5NDMgdXNlcnMsIDkzLjgyJSBEYXRhIGFyZSBOQS4NCmBgYHtyfQ0KcHJpbnQoZGltKGRmX3VzZXJfZmlsbSkpDQpwcmludChzdW0oaXMubmEoZGZfdXNlcl9maWxtKSkvKDE2NjMqOTQyKSkNCmBgYA0KYGBge3J9DQppbWFnZShhcyhkZl91c2VyX2ZpbG0sIm1hdHJpeCIpLCBtYWluID0gInNwYXJzaXR5IG9mIGRhdGFmcmFtZSBiZWZvcmUgcmVkdWN0aW9uIikNCmBgYA0KIyMjIE5hY2ggRGF0ZW5yZWR1a3Rpb246IDcwMCBNb3ZpZXMsIDQwMCB1c2VycywgNzUuOTAlIGRhdGEgYXJlIE5BLg0KDQpgYGB7cn0NCnByaW50KGRpbShkZl9yZWR1Y2VkKSkNCnByaW50KHN1bShpcy5uYShkZl9yZWR1Y2VkKSkvKDcwMCo0MDApKQ0KYGBgDQoNCmBgYHtyfQ0KaW1hZ2UoYXMoZGZfcmVkdWNlZCwibWF0cml4IiksbWFpbiA9ICJzcGFyc2l0eSBvZiBkYXRhZnJhbWUgYWZ0ZXIgcmVkdWN0aW9uIikNCmBgYA0KIyMjIFRoZSB0d28gaW1hZ2VzIGFib3ZlIHNob3dlZCB1cyB0aGUgZGF0YSBzcGFyc2l0eSBiZWZvcmUgKGZpcnN0IGltYWdlKSBhbmQgYWZ0ZXIgKHNlY29uZCBpbWFnZSkgcmVkdWN0aW9uLiBUaGUgYmxhbmsgcGl4ZWxzIHJlcHJlc2VudCB0aGUgTkEsIHRoZSBjb2xvciBwaXhlbHMgcmVwcmVzZW50IHRoZSBhdmFpbGFibGUgdmFsdWVzLiBCeSBjb21wYXJpbmcgdGhlIHR3byBpbWFnZXMsIHdlIGNvdWxkIHNlZSB0aGF0IHRoZSBmaXJzdCBpbWFnZSBoYXMgbW9yZSBibGFuayBhbmQgbGVzcyBjb2xvciBwaXhlbHMgdGhhbiB0aGUgc2Vjb25kIG9uZS4gVGhpcyBtZWFucyB0aGUgZGF0YSBhZnRlciByZWR1Y3Rpb24gaXMgbGVzcyBzcGFyc2UgdGhhbiBiZWZvcmUgcmVkdWN0aW9uLiBEYXRhIHJlZHVjdGlvbiBoYXMgc3VjY2Vzc2Z1bGx5IHJlZHVjZWQgdGhlIGRhdGEgc3BhcnNpdHkuDQoNCg0KDQozLjMgbWl0dGxlcmUgS3VuZGVucmF0aW5ncyBwcm8gRmlsbSB2b3IgdW5kIG5hY2ggRGF0ZW5yZWR1a3Rpb24uDQoNCiMjIyBCZWZvcmUgZGF0YSByZWR1Y3Rpb24NCg0KYGBge3J9DQpkZl9hdmdfcmF0aW5nIDwtIGRmX2ZpbG1fdXNlciAlPiUgbXV0YXRlKGF2Z19yYXRpbmcgPSByb3dNZWFucyhkZl9maWxtX3VzZXIsbmEucm0gPSBUUlVFLCBkaW1zID0gMSkpICU+JSBzZWxlY3QoJ2F2Z19yYXRpbmcnKQ0KZ2dwbG90KGRmX2F2Z19yYXRpbmcsYWVzKGF2Z19yYXRpbmcpKSArIGdlb21faGlzdG9ncmFtKGJpbndpZHRoID0gMC4yNSkgKyAgICAgICAgICAgICAgICAjIGRpZSBWZXJ0ZWlsdW5nDQogIGxhYnMoeD0iTWVhbiByYXRpbmdzIHBlciBmaWxtIiwgeT0iQ291bnQiLHRpdGxlPSJCZWZvcmUgcmVkdWN0aW9uOiBEaXN0cmlidXRpb24gb2YgdGhlIG1lYW4gcmF0aW5ncyBieSBmaWxtIikgKyANCiAgdGhlbWUocGxvdC50aXRsZSA9IGVsZW1lbnRfdGV4dChoanVzdCA9IDAuNSkpDQpgYGANCg0KYGBge3J9DQpkZl9yZWR1Y2VkX3QgPC0gYXMuZGF0YS5mcmFtZSh0KGRmX3JlZHVjZWQpKQ0KZGZfcmVkdWNlZF9hdmdfcmF0aW5nIDwtIGRmX3JlZHVjZWRfdCU+JSBtdXRhdGUoYXZnX3JhdGluZyA9IHJvd01lYW5zKGRmX3JlZHVjZWRfdCxuYS5ybSA9IFRSVUUsIGRpbXMgPSAxKSkgJT4lIHNlbGVjdCgnYXZnX3JhdGluZycpDQpnZ3Bsb3QoZGZfcmVkdWNlZF9hdmdfcmF0aW5nLGFlcyhhdmdfcmF0aW5nKSkgKyBnZW9tX2hpc3RvZ3JhbShiaW53aWR0aCA9IDAuMjUpICsgICAgICAgICAgICAgICAgIyBkaWUgVmVydGVpbHVuZw0KICBsYWJzKHg9Ik1lYW4gcmF0aW5ncyBwZXIgZmlsbSIsIHk9IkNvdW50Iix0aXRsZT0iQWZ0ZXIgcmVkdWN0aW9uOiBEaXN0cmlidXRpb24gb2YgdGhlIG1lYW4gcmF0aW5ncyBieSBmaWxtIikgKyANCiAgdGhlbWUocGxvdC50aXRsZSA9IGVsZW1lbnRfdGV4dChoanVzdCA9IDAuNSkpDQpgYGANCiMjIyBBZnRlciB0aGUgZGF0YSByZWR1Y3Rpb24sIHRoZSBhdmVyYWdlIHJhdGluZ3MgYXJlIGNsb3NlIHRvIGEgbGVmdCBza2V3ZWQgbm9ybWFsIGRpc3RyaWJ1dGlvbi4NCg0KDQoNCg0KNCBBbmFseXNlIMOEaG5saWNoa2VpdHNtYXRyaXgNCg0KNC4xIFplcmxlZ2UgZGVuIHJlZHV6aWVydGVuIE1vdmllTGVuc2UgRGF0ZW5zYXR6IGluIGVpbiBkaXNqdW5rdGUgVHJhaW5pbmdzLXVuZCBUZXN0ZGF0ZW5zZXQgaW0gVmVyaMOkbHRuaXMgNDoxDQoNCmBgYHtyfQ0Kc2V0LnNlZWQoNDY1KQ0KbXhfcmVkdWNlZCA8LSBhcy5tYXRyaXgoZGZfcmVkdWNlZCkNCnJybV9yZWR1Y2VkIDwtIGFzKG14X3JlZHVjZWQsInJlYWxSYXRpbmdNYXRyaXgiKQ0KdHJhaW5fdGVzdCA8LSBldmFsdWF0aW9uU2NoZW1lKHJybV9yZWR1Y2VkLCBtZXRob2Q9InNwbGl0IiwgdHJhaW49MC44LCBrPTEsIGdpdmVuPTIwLCBnb29kUmF0aW5nPTQpDQoNCiMgdHJhaW5pbmcgZGF0YSA4MCUgb2YgdGhlIHVzZXJzDQpycm1fcmVkdWNlZF90cmFpbiA8LSBnZXREYXRhKHRyYWluX3Rlc3QsInRyYWluIikNCg0KDQojIHRlc3QgZGF0YSBpcyAyMCUgb2YgdGhlIGFsbCB1c2VycywgdGhlIHRlc3QgZGF0YSBpcyBzcGxpdGVkIGludG8gdHdvIHBhcnRzOiBrbm93biB0ZXN0IGRhdGEgYW5kIHVua25vd24gdGVzdCBkYXRhDQoNCiMgdGhlIGtub3duIHBvcnRpb24gcmV0dXJucyBzcGVjaWZpZWQgMjAgaXRlbXMgcGVyIHRlc3QgdXNlciBpcyB1c2VkIHRvIHByZWRpY3QgcmF0aW5ncyBvciBmaWxtcyBmb3IgdGhlIHRlc3QgdXNlcnMNCnJybV9yZWR1Y2VkX2tub3duIDwtIGdldERhdGEodHJhaW5fdGVzdCwia25vd24iKQ0KDQoNCiMgdGhlIHVua25vd24gcG9ydGlvbiBpcyB1c2VkIHRvIGNvbXB1dGUgdGhlIHByZWRpY3Rpb24gZXJyb3Igb2YgdGhlIG1vZGVsDQpycm1fcmVkdWNlZF91bmtub3duIDwtIGdldERhdGEodHJhaW5fdGVzdCwidW5rbm93biIpDQoNCmBgYA0KDQo0LjIgVHJhaW5pZXJlIGVpbiBJQkNGIE1vZGVsbCBtaXQgMzAgTmFjaGJhcm4gdW5kIENvc2luZSBTaW1pbGFyaXR5DQoNCmBgYHtyfQ0KbW9kZWxfSUJDRiA8LSBSZWNvbW1lbmRlcihkYXRhID0gcnJtX3JlZHVjZWRfdHJhaW4sbWV0aG9kPSJJQkNGIixwYXJhbWV0ZXI9bGlzdChub3JtYWxpemUgPSAiWi1zY29yZSIsbWV0aG9kPSJDb3NpbmUiLGs9MzApKSANCg0KYGBgDQoNCjQuMyBCZXN0aW1tZSBkaWUgVmVydGVpbHVuZyBkZXIgRmlsbWUsIHdlbGNoZSBiZWkgSUJDRiBmw7xyIHBhYXJ3ZWlzZSDDhGhubGljaGtlaXRzdmVyZ2xlaWNoZSB2ZXJ3ZW5kZXQgd2VyZGVuLg0KRGV0ZXJtaW5lIHRoZSBkaXN0cmlidXRpb24gb2YgZmlsbXMgdXNlZCBpbiBJQkNGIGZvciBwYWlyd2lzZSBzaW1pbGFyaXR5IGNvbXBhcmlzb25zDQoNCmBgYHtyfQ0KIyBIZXJlIG9ubHkgZXhoaWJpdCB0aGUgZmlyc3QgNTAgcm93cyBhbmQgY29sdW1ucw0KZ2V0X21vZGVsX0lCQ0YgPC0gZ2V0TW9kZWwobW9kZWxfSUJDRikgDQppbWFnZShnZXRfbW9kZWxfSUJDRiRzaW1bMTo1MCwgMTo1MF0sIG1haW4gPSAiU2ltaWxhcml0eSBvZiB0aGUgZmlyc3QgNTAgcm93cyBhbmQgY29sdW1ucyIpDQoNCmBgYA0KDQojIyMgVGhlIHNpbWlsYXJpdHkgbWF0cml4IGlzIG5vdCBzeW1tZXRyaWMuIEVhY2ggcm93IGhhcyAzMCBlbGVtZW50cyBsYXJnZXIgdGhhbiAwLiBJbiBlYWNoIGNvbHVtbiwgdGhlIG51bWJlciBvZiBlbGVtZW50cyBncmVhdGVyIHRoYW4gMCBpbmRpY2F0ZXMgaG93IG1hbnkgdGltZXMgdGhpcyBmaWxtIHdhcyBpbmNsdWRlZCBpbiB0aGUgVE9QIGxpc3Qgb2Ygb3RoZXIgZmlsbXMuDQoNCmBgYHtyfQ0KSUJDRl9zaW0gPC0gYXMuZGF0YS5mcmFtZShjb2xTdW1zKGdldF9tb2RlbF9JQkNGJHNpbSA+IDApKSANCmNvbG5hbWVzKElCQ0Zfc2ltKSA8LSAicmVjb21tZW5kZWRfZnJlcXVlbmN5IiAjIGZyZXF1ZW5jeSB0aGF0IHRoZSBjb3JyZXNwb25kaW5nIGZpbG0gaXMgaW5jbHVkZWQgaW4gb3RoZXIgZmlsbXMnIFRPUC1OIGxpc3RzDQoNCmdncGxvdChJQkNGX3NpbSwgYWVzKHg9SUJDRl9zaW0kcmVjb21tZW5kZWRfZnJlcXVlbmN5KSkrZ2VvbV9oaXN0b2dyYW0oZmlsbD0iYmxhY2siLCBjb2w9ImdyZXkiLGJpbndpZHRoID0gNSkrDQogIGxhYnMoeCA9ICJSZWNvbW1lbmRlZCBmcmVxdWVuY3kiLCB5ID0gIkNvdW50IiwgdGl0bGUgPSAiRGlzdHJpYnV0aW9uIG9mIHJlY29tbWVuZGVkIGZyZXF1ZW5jeSBwZXIgZmlsbSIpICsNCiAgdGhlbWUocGxvdC50aXRsZSA9IGVsZW1lbnRfdGV4dChoanVzdCA9IDAuNSkpDQoNCmBgYA0KIyMjIFRoZSBwbG90IGRpc3BsYXlzIHRoZSBkaXN0cmlidXRpb24gb2YgZmlsbXMgYnkgaG93IG1hbnkgdGltZXMgdGhlIGNvcnJlc3BvbmRpbmcgZmlsbSBpbmNsdWRlZCBpbiB0aGUgVE9QIGxpc3Qgb2Ygb3RoZXIgZmlsbXMuIEZvciBpbnN0YW5jZSwgYWJvdXQgNTIgZmlsbXMgYXJlIG5vdCBpbmNsdWRlZCBpbiBhbnkgVE9QIGxpc3Qgb2Ygb3RoZXIgZmlsbXMsIGFib3V0IDEwMCBmaWxtcyBhcmUgaW5jbHVkZWQgaW4gdGhlIFRPUCBsaXN0cyBvZiA1IGZpbG1zLiBUaGUgaGlnaGVzdCBmcmVxdWVuY3kgaXMgYWJvdXQgMTYwLg0KDQoNCg0KNC40IEJlc3RpbW1lIGRpZSBGaWxtZSwgZGllIGFtIGjDpHVmaWdzdGVuIGluIGRlciBDb3NpbmUtw4RobmxpY2hrZWl0c21hdHJpeCBhdWZ0YXVjaGVuIHVuZCBhbmFseXNpZXJlIGRlcmVuIFZvcmtvbW1lbiB1bmQgUmF0aW5ncyBpbSByZWR1emllcnRlbiBEYXRlbnNhdHouIA0KDQojIyMgZGllIGFtIGjDpHVmaWdzdGVuIEZpbG0gaW4gZGVyIENvc2luZS3DhGhubGljaGtlaXRzbWF0cml4IA0KYGBge3J9DQojIGRpZSAxMCBhbSBow6R1Zmlnc3RlbiBGaWxtZSBpbiBkZXIgQ29zaW5lIMOEaG5saWNoa2VpdHNtYXRyaXgsIGkuZS4gZGllIEZpbG1lIG1pdCBkZXIgaMO2aGVzdGUgc3VtIMOEaG5saWNoa2VpdHMNCmhpZ2hfZnJlcV9maWxtIDwtIElCQ0Zfc2ltICU+JSBtdXRhdGUoZmlsbSA9IHJvd25hbWVzKElCQ0Zfc2ltKSkgJT4lIGFycmFuZ2UoZGVzYyhyZWNvbW1lbmRlZF9mcmVxdWVuY3kpKSAlPiUgc2xpY2UoMDoxMCkgICU+JSBzZWxlY3QoZmlsbSxyZWNvbW1lbmRlZF9mcmVxdWVuY3kpDQpoaWdoX2ZyZXFfZmlsbSANCmBgYA0KIyMjIFRoZSBNb3VzZSBIdW50IGlzIHRoZSBtb3N0IG9mdGVuIHJlY29tbWVuZGVkIGZpbG0uDQoNCg0KDQojIyMgZGllIFZvcmtvbW1lbiB1bmQgUmF0aW5ncyBpbiByZWR1emllcnRlbiBEYXRlbnNhdHoNCmBgYHtyfQ0KdCA8LSBkZl9yZWR1Y2VkX3QgJT4lIG11dGF0ZShpc19OQSA9IHJvd1N1bXMoaXMubmEoZGZfcmVkdWNlZF90KSksbm90X05BID0gcm93U3VtcyghaXMubmEoZGZfcmVkdWNlZF90KSksb2NjdXJyZW5jZSA9IHJvd1N1bXMoIWlzLm5hKGRmX3JlZHVjZWRfdCkpL2RpbShkZl9yZWR1Y2VkX3QpWzJdLCBmaWxtID0gcm93bmFtZXMoZGZfcmVkdWNlZF90KSkgJT4lIHNlbGVjdChpc19OQSxub3RfTkEsb2NjdXJyZW5jZSxmaWxtKQ0KT2NjdXJyZW5jZSA8LSBsZWZ0X2pvaW4oaGlnaF9mcmVxX2ZpbG0sdCxieSA9ICJmaWxtIikgJT4lIHNlbGVjdChmaWxtLHJlY29tbWVuZGVkX2ZyZXF1ZW5jeSxvY2N1cnJlbmNlKSANCnQyIDwtIGRmX3JlZHVjZWRfdCAlPiUgbXV0YXRlKGZpbG0gPSByb3duYW1lcyhkZl9yZWR1Y2VkX3QpLCBhdmdfcmF0aW5nID0gcm93TWVhbnMoZGZfcmVkdWNlZF90LG5hLnJtPVRSVUUpKSU+JSBzZWxlY3QoZmlsbSxhdmdfcmF0aW5nKQ0KT2NjdXJyZW5jZSA8LSBsZWZ0X2pvaW4oT2NjdXJyZW5jZSx0MixieSA9ICJmaWxtIikNCk9jY3VycmVuY2UgICMgb2NjdXJyZW5jZTogbm90X05BIC8gdXNlciBudW1iZXIsIHRoZSB1c2VyIHJhdGlvIHRoYXQgcmF0ZWQgdGhpcyBmaWxtDQpgYGANCiMjIyByZWNvbW1lbmRlZF9mcmVxdWVuY3k6IHRoZSBmcmVxdWFuZWN5IHRoYXQgdGhpcyBpdGVtIGFwcGVhcnMgaW4gdGhlIHRvcC1uIHJlY29tbWVuZGF0aW9uIGxpc3Qgb2Ygb3RoZXIgdXNlcnMuIA0KIyMjIG9jY3VycmVuY2U6IHJhdGlvIHRoYXQgdGhlIGZpbG0gaXMgcmF0ZWQgdG8gYWxsIHVzZXJzDQojIyMgYXZnX3JhdGluZzogdGhlIGF2ZXJhZ2UgcmF0aW5nIG9mIGVhY2ggZmlsbQ0KIyMjIEZyb20gdGhlIHJlc3VsdCwgd2UgY291bGQgc2VlIHRoYXQsIHRoZXJlIGFyZSBubyBkaXJlY3QgcmVsYXRpb25zaGlwIGJldHdlZW4gdGhlIHRocmVlIHZhcmlhYmxlcy4gVGhlIG1vc3Qgb2Z0ZW4gcmVjb21tZW5kZWQgZmlsbSBNb3VzZSBIdW50IGhhcyBhIHJlbGF0aXZlbHkgbG93IGF2ZXJhZ2UgcmF0aW5nIDIuMzIsIGFuZCBtZWRpdW0gb2NjdXJyZW5jZS4NCg0KDQoNCjUgQW5hbHlzZSBUb3AtTiBMaXN0ZW4gSUJDRiB2cyBVQkNGIFZlcmdsZWljaGUgdW5kIGRpc2t1dGllcmUgVG9wIE4gRW1wZmVobHVuZ2VuIHZvbiBJQkNGIHVuZCBVQkNGIE1vZGVsbGVuIG1pdCAzMCBOYWNoYmFybiB1bmQgQ29zaW5lIFNpbWlsYXJpdHkgZsO8ciBkZW4gcmVkdXppZXJ0ZW4gRGF0ZW5zYXR6Lg0KQW5hbHlzaXMgVG9wLU4gbGlzdHMgSUJDRiB2cyBVQkNGLiBDb21wYXJlIGFuZCBkaXNjdXNzIHRvcCBOIHJlY29tbWVuZGF0aW9ucyBmcm9tIElCQ0YgYW5kIFVCQ0YgbW9kZWxzIHdpdGggMzAgbmVpZ2hib3JzIGFuZCBjb3NpbmUgc2ltaWxhcml0eSBmb3IgdGhlIHJlZHVjZWQgZGF0YSBzZXQuDQoNCjUuMSBCZXJlY2huZSBUb3AgMTUgRW1wZmVobHVuZ2VuIGbDvHIgVGVzdGt1bmRlbiBtaXQgSUJDRiB1bmQgVUJDRg0KDQpgYGB7cn0NCiMjIHRvcC1OIHJlY29tbWVuZGF0aW9ucyBmb3IgdGVzdGRhdGEgdXNlcnMgd2l0aCBJQkNGDQpQcmVkX0lCQ0YgPC0gcHJlZGljdChvYmplY3QgPSBtb2RlbF9JQkNGLCBuZXdkYXRhID0gcnJtX3JlZHVjZWRfa25vd24sIG4gPSAxNSx0eXBlPWMoInRvcE5MaXN0IikpDQoNClRPUDE1X0lCQ0YgPC0gc2FwcGx5KFByZWRfSUJDRkBpdGVtcywgZnVuY3Rpb24oeCkge2NvbG5hbWVzKGRmX3JlZHVjZWQpW3hdfSkNClRPUDE1X0lCQ0ZbLDE6Ml0gICMgaGVyZSBvbmx5IGRpc3BsYXkgdGhlIHRvcCAxNSByZWNvbW1lbmRhdGlvbnMgZm9yIHRoZSBmaXJzdCB0d28gdGVzdCB1c2Vycw0KYGBgDQoNCg0KYGBge3J9DQojIHByZWRpY3Qgd2l0aCBVQkNGDQptb2RlbF9VQkNGIDwtIFJlY29tbWVuZGVyKHJybV9yZWR1Y2VkX3RyYWluLG1ldGhvZD0iVUJDRiIscGFyYW09bGlzdChub3JtYWxpemUgPSAiWi1zY29yZSIsbWV0aG9kPSJDb3NpbmUiLG5uPTMwKSkgI21vZGVsDQojIHRvcC1OIHJlY29tbWVuZGF0aW9ucyBmb3IgdGVzdGRhdGEgdXNlcnMgd2l0aCBVQkNGDQpQcmVkX1VCQ0YgPC0gcHJlZGljdChvYmplY3QgPSBtb2RlbF9VQkNGLCBuZXdkYXRhID0gcnJtX3JlZHVjZWRfa25vd24sIG4gPSAxNSx0eXBlPWMoInRvcE5MaXN0IikpIA0KI1RPUDE1X1VCQ0YgPC0gYXMoUHJlZF9VQkNGLCAibGlzdCIpDQpUT1AxNV9VQkNGIDwtIHNhcHBseShQcmVkX1VCQ0ZAaXRlbXMsIGZ1bmN0aW9uKHgpIHtjb2xuYW1lcyhkZl9yZWR1Y2VkKVt4XX0pDQpUT1AxNV9VQkNGWywxOjJdICMgaGVyZSBvbmx5IGRpc3BsYXkgdGhlIHRvcCAxNSByZWNvbW1lbmRhdGlvbnMgZm9yIHRoZSBmaXJzdCB0d28gdGVzdCB1c2Vycw0KYGBgDQoNCjUuMiBWZXJnbGVpY2hlIGRpZSBUb3AgMTUgRW1wZmVobHVuZ2VuIHVuZCBkZXJlbiBWZXJ0ZWlsdW5nIHVuZCBkaXNrdXRpZXJlIEdlbWVpbnNhbWtlaXRlbiB1bmQgVW50ZXJzY2hpZWRlIHp3aXNjaGVuIElCQ0YgdW5kIFVCQ0YgZsO8ciBhbGxlIFRlc3RrdW5kZW4uDQoNCiMjIyBGcm9tIGFib3ZlIHRoZSByZXN1bHQgZm9yIGZpcnN0IHR3byB1c2Vycywgd2UgY291bGQgc2VlIHRoYXQgdGhlIHRvcCAxNSByZWNvbW1lbmRhdGlvbnMgZm9yIHRoZSBzYW1lIHVzZXIgYmV0d2VlbiB0aGUgSUJDRiBhbmQgVUJDRiBtb2RlbHMgYXJlIGNvbXBsZXRlbHkgZGlmZmVyZW50Lg0KDQoNCkNvbXBhcmUgdGhlIHRvcCAxNSByZWNvbW1lbmRhdGlvbnMgZm9yIGFsbCB0ZXN0IHVzZXJzIA0KRmlyc3QgaWRlbnRpZnkgdGhlIG1vc3QgcmVjb21tZW5kZWQgbW92aWVzIGluIHRoZSBUT1AtMTUgbGlzdCBmcm9tIGFsbCB0ZXN0IHVzZXJzLiANCmBgYHtyfQ0KIyBnZW5lcmF0ZSBmcmVxdWVuY3kgdGFibGVzIDogYWxsIHRoZSByZWNvbW1lbmRhdGlvbiBmaWxtcyB3aXRoIHRoZSBjb3JyZXNwb25kaW5nIGZyZXF1ZW5jaWVzIA0KDQpmaWxtX2ZyZXFfSUJDRiA8LSBhcy5kYXRhLmZyYW1lKHRhYmxlKGFzLmZhY3RvcihUT1AxNV9JQkNGKSkpIA0KY29sbmFtZXMoZmlsbV9mcmVxX0lCQ0YpIDwtIGMoIkZpbG1fYnlfSUJDRiIsICJGcmVxdWVuY3kiKSANCg0KZmlsbV9mcmVxX1VCQ0YgPC0gYXMuZGF0YS5mcmFtZSh0YWJsZShhcy5mYWN0b3IoVE9QMTVfVUJDRikpKQ0KY29sbmFtZXMoZmlsbV9mcmVxX1VCQ0YpIDwtIGMoIkZpbG1fYnlfVUJDRiIsICJGcmVxdWVuY3kiKQ0KDQpoZWFkKGZpbG1fZnJlcV9JQkNGICU+JSBhcnJhbmdlKGRlc2MoRnJlcXVlbmN5KSksMTUpDQpoZWFkKGZpbG1fZnJlcV9VQkNGICU+JSBhcnJhbmdlKGRlc2MoRnJlcXVlbmN5KSksMTUpDQpgYGANCg0KYGBge3J9DQpnZ3Bsb3QoaGVhZChmaWxtX2ZyZXFfSUJDRiAlPiUgYXJyYW5nZShkZXNjKEZyZXF1ZW5jeSkpLDE1KSxhZXMoeCA9IHJlb3JkZXIoRmlsbV9ieV9JQkNGLEZyZXF1ZW5jeSksIHkgPSBGcmVxdWVuY3kpKSArIGdlb21fY29sKCkgKyBjb29yZF9mbGlwKCkgKw0KICBsYWJzKHk9IkZyZXF1ZW5jeSIsIHg9IkZpbG0iLHRpdGxlPSJEaXN0cmlidXRpb24gb2YgdGhlIFRvcC0xNSBmaWxtcyBmb3IgYWxsIHRoZSB1c2VycyB3aXRoIElCQ0YiKSArIA0KICB0aGVtZShwbG90LnRpdGxlID0gZWxlbWVudF90ZXh0KGhqdXN0ID0gMC41KSkNCmBgYA0KDQpgYGB7cn0NCmdncGxvdChoZWFkKGZpbG1fZnJlcV9VQkNGICU+JSBhcnJhbmdlKGRlc2MoRnJlcXVlbmN5KSksMTUpLGFlcyh4ID0gcmVvcmRlcihGaWxtX2J5X1VCQ0YsRnJlcXVlbmN5KSwgeSA9IEZyZXF1ZW5jeSkpICsgZ2VvbV9jb2woKSArIGNvb3JkX2ZsaXAoKSArDQogIGxhYnMoeT0iRnJlcXVlbmN5IiwgeD0iRmlsbSIsdGl0bGU9IkRpc3RyaWJ1dGlvbiBvZiB0aGUgVG9wLTE1IGZpbG1zIGZvciBhbGwgdGhlIHVzZXJzIHdpdGggVUJDRiIpICsgDQogIHRoZW1lKHBsb3QudGl0bGUgPSBlbGVtZW50X3RleHQoaGp1c3QgPSAwLjUpKQ0KYGBgDQoNCiMjIyBUaGUgbWF4aW11bSByZWNvbW1lbmRlZCBmcmVxdWVuY3kgd2l0aCBJQkNGIGFuZCBVQkNGIGFyZSAyNiBhbmQgMjggcmVzcGVjdGl2ZWx5LCBhbmQgbWluaW11bSBvZiAxNSBhbmQgMTMuIEhvd2V2ZXIgY29tcGFyaW5nIHRvIHRoZSBJQkNGLCB0aGUgZGlzdHJpYnV0aW9uIGluIFVCQ0YgaGFzIGEgbG9uZ2VyIHRhaWwuIFRoaXMgbWVhbnMgd2l0aCB0aGUgVUJDRiBtb2RlbCwgc29tZSBtb3ZpZXMgYXJlIHJlY29tbWVuZGVkIG11Y2ggbW9yZSBvZnRlbiB0aGFuIHRoZSBvdGhlcnMuDQoNCg0KNiBBbmFseXNlIFRvcC1OIExpc3RlbiBSYXRpbmdzDQpVbnRlcnN1Y2hlIGRlbiBFaW5mbHVzcyB2b24gUmF0aW5ncyAob3JkaW5hbGUgdnMgYmluw6RyZSBSYXRpbmdzKSB1bmQgTW9kZWxsdHlwIChJQkNGIHZzIFVCQ0YpIGF1ZiBUb3AgTiBFbXBmZWhsdW5nZW4gZsO8ciBkZW4gcmVkdXppZXJ0ZW4gRGF0ZW5zYXR6Lg0KDQo2LjEgVmVyZ2xlaWNoZSBkZW4gQW50ZWlsIMO8YmVyZWluc3RpbW1lbmRlciBFbXBmZWhsdW5nZW4gZGVyIFRvcCAxNSBMaXN0ZSBmw7xyIElCQ0YgdnMgVUJDRiwgYmVpZGUgbWl0IG9yZGluYWxlbSBSYXRpbmcgdW5kIENvc2luZSBTaW1pbGFyaXR5IGbDvHIgYWxsZSBUZXN0a3VuZGVuDQoNCmBgYHtyfQ0KIyB0aGUgdGVzdCB1c2VyICJ1bmtub3duIiByYXRpbmdzDQpteF9yZWR1Y2VkX3Vua25vd24gPC0gYXMocnJtX3JlZHVjZWRfdW5rbm93biwibWF0cml4IikNCg0KIyBwcmVkaWN0IHRoZSByYXRpbmdzIG9mIHRlc3QgdXNlcnMgYnkgSUJDRiBhbmQgVUJDRg0KcHJlZF9yYXRpbmdfSUJDRiA8LSBhcyhwcmVkaWN0KG9iamVjdCA9IG1vZGVsX0lCQ0YsIG5ld2RhdGEgPSBycm1fcmVkdWNlZF9rbm93biwgbiA9IDE1LHR5cGU9InJhdGluZ3MiKSwibWF0cml4IikNCnByZWRfcmF0aW5nX1VCQ0YgPC0gYXMocHJlZGljdChvYmplY3QgPSBtb2RlbF9VQkNGLCBuZXdkYXRhID0gcnJtX3JlZHVjZWRfa25vd24sIG4gPSAxNSx0eXBlPSJyYXRpbmdzIiksIm1hdHJpeCIpDQoNCiMgZXZhbHVhdGUgcmVjb21tZW5kYXRpb25zIG9uICJ1bmtub3duIiByYXRpbmdzDQphY2NfSUIgPC0gY2FsY1ByZWRpY3Rpb25BY2N1cmFjeShwcmVkaWN0KG9iamVjdCA9IG1vZGVsX0lCQ0YsIG5ld2RhdGEgPSBycm1fcmVkdWNlZF9rbm93biwgbiA9IDE1LHR5cGU9InJhdGluZ3MiKSxycm1fcmVkdWNlZF91bmtub3duKQ0KYWNjX1VCIDwtIGNhbGNQcmVkaWN0aW9uQWNjdXJhY3kocHJlZGljdChvYmplY3QgPSBtb2RlbF9VQkNGLCBuZXdkYXRhID0gcnJtX3JlZHVjZWRfa25vd24sIG4gPSAxNSx0eXBlPSJyYXRpbmdzIikscnJtX3JlZHVjZWRfdW5rbm93bikNCmFjY19vcmRpbmFsIDwtIHJiaW5kKGFjY19JQixhY2NfVUIpDQpyb3duYW1lcyhhY2Nfb3JkaW5hbCkgPC0gYygiSUJDRiBvcmRpbmFsIiwiVUJDRiBvcmRpbmFsIikNCmFjY19vcmRpbmFsDQpgYGANCiMjIyB0aGUgVUJDRiBtb2RlbCB3aXRoIG9yZGluYWwgcmF0aW5ncyBhbmQgY29zaW5lIHNpbWlsYXJpdHkgaGFzIGJldHRlciBhY2N1cmFjeS4NCg0KDQo2LjIgVmVyZ2xlaWNoZSBkZW4gQW50ZWlsIMO8YmVyZWluc3RpbW1lbmRlciBFbXBmZWhsdW5nZW4gZGVyIFRvcCAxNSBMaXN0ZSBmw7xyIElCQ0YgdnMgVUJDRiwgYmVpZGUgbWl0IGJpbsOkcmVtIFJhdGluZyB1bmQgSmFjY2FyZCBTaW1pbGFyaXR5IGbDvHIgYWxsZSBUZXN0a3VuZGVuDQoNCmBgYHtyfQ0KIyBjb252ZXJ0IHRoZSByZWR1Y2VkIGRhdGFzZXQgdG8gYmluYXJ5OiByYXRpbmdzID4gMyBjb252ZXJ0ZWQgYXMgMSwgcmF0aW5ncyA8PSAzIGNvbnZlcnRlZCBhcyAwIA0KZGZfcmVkdWNlZF9iaSA8LSBkZl9yZWR1Y2VkDQpkZl9yZWR1Y2VkX2JpW2RmX3JlZHVjZWRfYmkgPD0gM10gPC0gMA0KZGZfcmVkdWNlZF9iaVtkZl9yZWR1Y2VkX2JpID4gM10gPC0gMQ0KDQpzZXQuc2VlZCg0NjgpDQpteF9yZWR1Y2VkX2JpIDwtIGFzLm1hdHJpeChkZl9yZWR1Y2VkX2JpKQ0KcnJtX3JlZHVjZWRfYmkgPC0gYXMobXhfcmVkdWNlZF9iaSwicmVhbFJhdGluZ01hdHJpeCIpDQp0cmFpbl90ZXN0X2JpIDwtIGV2YWx1YXRpb25TY2hlbWUocnJtX3JlZHVjZWRfYmksIG1ldGhvZD0ic3BsaXQiLCB0cmFpbj0wLjgsIGs9MSwgZ2l2ZW49MjApDQoNCiMgdHJhaW5pbmcgZGF0YSA4MCUgb2YgdGhlIHVzZXJzDQpycm1fcmVkdWNlZF90cmFpbl9iaSA8LSBnZXREYXRhKHRyYWluX3Rlc3RfYmksInRyYWluIikNCg0KIyB0ZXN0IGRhdGEgaXMgMjAlIG9mIHRoZSBhbGwgdXNlcnMsIHRoZSB0ZXN0IGRhdGEgaXMgc3BsaXRlZCBpbnRvIHR3byBwYXJ0czoga25vd24gdGVzdCBkYXRhIGFuZCB1bmtub3duIHRlc3QgZGF0YQ0KIyB0aGUga25vd24gcG9ydGlvbiByZXR1cm5zIHNwZWNpZmllZCAyMCBpdGVtcyBwZXIgdGVzdCB1c2VyIGlzIHVzZWQgdG8gcHJlZGljdCByYXRpbmdzIG9yIGZpbG1zIGZvciB0aGUgdGVzdCB1c2Vycw0KcnJtX3JlZHVjZWRfa25vd25fYmkgPC0gZ2V0RGF0YSh0cmFpbl90ZXN0X2JpLCJrbm93biIpDQoNCiMgdGhlIHVua25vd24gcG9ydGlvbiBpcyB1c2VkIHRvIGNvbXB1dGUgdGhlIHByZWRpY3Rpb24gZXJyb3Igb2YgdGhlIG1vZGVsDQpycm1fcmVkdWNlZF91bmtub3duX2JpIDwtIGdldERhdGEodHJhaW5fdGVzdF9iaSwidW5rbm93biIpDQoNCiMgdHJhaW4gdGhlIElCQ0Ygb3IgVUJDRiBtb2RlbCBvbiB0cmFpbmluZyBkYXRhc2V0DQptb2RlbF9JQkNGX2JpIDwtIFJlY29tbWVuZGVyKGRhdGEgPSBycm1fcmVkdWNlZF90cmFpbl9iaSxtZXRob2Q9IklCQ0YiLHBhcmFtZXRlcj1saXN0KG5vcm1hbGl6ZSA9ICJaLXNjb3JlIixtZXRob2Q9IkphY2NhcmQiLGs9MzApKQ0KbW9kZWxfVUJDRl9iaSA8LSBSZWNvbW1lbmRlcihkYXRhID0gcnJtX3JlZHVjZWRfdHJhaW5fYmksbWV0aG9kPSJVQkNGIixwYXJhbWV0ZXI9bGlzdChub3JtYWxpemUgPSAiWi1zY29yZSIsbWV0aG9kPSJKYWNjYXJkIixubj0zMCkpDQoNCiMgcHJlZGljdCB0aGUgcmF0aW5ncyBvZiB0ZXN0IHVzZXJzIGJ5IElCQ0YgYW5kIFVCQ0YNCnByZWRfcmF0aW5nX0lCQ0ZfYmkgPC0gYXMocHJlZGljdChvYmplY3QgPSBtb2RlbF9JQkNGX2JpLCBuZXdkYXRhID0gcnJtX3JlZHVjZWRfa25vd25fYmksIG4gPSAxNSx0eXBlPSJyYXRpbmdzIiksIm1hdHJpeCIpDQpwcmVkX3JhdGluZ19VQkNGX2JpIDwtIGFzKHByZWRpY3Qob2JqZWN0ID0gbW9kZWxfVUJDRl9iaSwgbmV3ZGF0YSA9IHJybV9yZWR1Y2VkX2tub3duX2JpLCBuID0gMTUsdHlwZT0icmF0aW5ncyIpLCJtYXRyaXgiKQ0KDQojIHRoZSB0ZXN0IHVzZXIgInVua25vd24iIHJhdGluZ3MNCm14X3JlZHVjZWRfdW5rbm93bl9iaSA8LSBhcyhycm1fcmVkdWNlZF91bmtub3duX2JpLCJtYXRyaXgiKQ0KDQojIGV2YWx1YXRlIHJlY29tbWVuZGF0aW9ucyBvbiAidW5rbm93biIgcmF0aW5ncw0KYWNjX0lCX2JpIDwtIGNhbGNQcmVkaWN0aW9uQWNjdXJhY3kocHJlZGljdChvYmplY3QgPSBtb2RlbF9JQkNGX2JpLCBuZXdkYXRhID0gcnJtX3JlZHVjZWRfa25vd25fYmksIG4gPSAxNSx0eXBlPSJyYXRpbmdzIikscnJtX3JlZHVjZWRfdW5rbm93bl9iaSkNCmFjY19VQl9iaSA8LSBjYWxjUHJlZGljdGlvbkFjY3VyYWN5KHByZWRpY3Qob2JqZWN0ID0gbW9kZWxfVUJDRl9iaSwgbmV3ZGF0YSA9IHJybV9yZWR1Y2VkX2tub3duX2JpLCBuID0gMTUsdHlwZT0icmF0aW5ncyIpLHJybV9yZWR1Y2VkX3Vua25vd25fYmkpDQphY2NfYmkgPC0gcmJpbmQoYWNjX0lCX2JpLGFjY19VQl9iaSkNCnJvd25hbWVzKGFjY19iaSkgPC0gYygiSUJDRiBiaW5hcnkiLCJVQkNGIGJpbmFyeSIpDQphY2NfYmkNCmBgYA0KIyMjIHRoZSBVQkNGIG1vZGVsIHdpdGggYmluYXJ5IHJhdGluZ3MgYW5kIGNvc2luZSBzaW1pbGFyaXR5IGhhcyBiZXR0ZXIgYWNjdXJhY3kuDQoNCg0KNi4zIFZlcmdsZWljaGUgZGVuIEFudGVpbCDDvGJlcmVpbnN0aW1tZW5kZXIgRW1wZmVobHVuZ2VuIGRlciBUb3AgMTUgTGlzdGUgZsO8ciBVQkNGIG1pdCBvcmRpbmFsZW0gKENvc2luZSBTaW1pbGFyaXR5KSB2cyBiaW7DpHJlbSBSYXRpbmcgKEphY2NhcmQgU2ltaWxhcml0eSkgZsO8ciBhbGxlIFRlc3RrdW5kZW4uDQoNCmBgYHtyfQ0KcmJpbmQoYWNjX29yZGluYWwsYWNjX2JpKQ0KYGBgDQojIyMgVGhlIG1vZGVsIHdpdGggYmluYXJ5IHJhdGluZ3MgaGF2ZSBsYXJnZWx5IGltcHJvdmVkIHRoZSBhY2N1cmFjeSBjb21wYXJpbmcgdG8gdGhlIG1vZGVscyB3aXRoIG9yZGluYWwgcmF0aW5ncy4NCg0KDQo3ICBBbmFseXNlIFRvcC1OIExpc3RlbiAtSUJDRiB2cyBTVkQNCkF1ZmdhYmU6IFZlcmdsZWljaGUgTWVtb3J5LWJhc2VkIElCQ0YgdW5kIE1vZGVsbC1iYXNlZCBTVkQgUmVjb21tZW5kZXJzIGJlesO8Z2xpY2ggw5xiZXJzY2huZWlkdW5nIGlocmVyIFRvcC1OIEVtcGZlaGx1bmdlbg0KZsO8ciBkaWUgVXNlci1JdGVtIE1hdHJpeCBkZXMgcmVkdXppZXJ0ZW4gRGF0ZW5zYXR6ZXMgKEJhc2lzOiBJQkNGIG1pdCAzMCBOYWNoYmFybiB1bmQgQ29zaW5lIFNpbWlsYXJpdHkpLg0KDQoxLiBWZXJnbGVpY2hlIHdpZSBzaWNoIGRlciBBbnRlaWwgw7xiZXJlaW5zdGltbWVuZGVyIEVtcGZlaGx1bmdlbiBkZXIgVG9wLTE1IExpc3RlIGbDvHIgSUJDRiB2cyB2ZXJzY2hpZWRlbmUgU1ZEIE1vZGVsbGUgdmVyw6RuZGVydCwgd2VubiBkaWUgQW56YWhsIGRlciBTaW5ndWzDpHJ3ZXJ0ZSBmw7xyIFNWRCB2b24gMTAgYXVmIDIwLCAzMCwgNDAsIDUwIHZlcsOkbmRlcnQgd2lyZC4NCg0KYGBge3J9DQoNCiMgU1ZEIE1PREVMDQptb2RlbF9TVkRfMTAgPC0gUmVjb21tZW5kZXIoZGF0YSA9IHJybV9yZWR1Y2VkX3RyYWluLG1ldGhvZD0iU1ZEIixwYXJhbWV0ZXI9bGlzdChub3JtYWxpemUgPSAiWi1zY29yZSIsaz0xMCkpDQptb2RlbF9TVkRfMjAgPC0gUmVjb21tZW5kZXIoZGF0YSA9IHJybV9yZWR1Y2VkX3RyYWluLG1ldGhvZD0iU1ZEIixwYXJhbWV0ZXI9bGlzdChub3JtYWxpemUgPSAiWi1zY29yZSIsaz0yMCkpDQptb2RlbF9TVkRfMzAgPC0gUmVjb21tZW5kZXIoZGF0YSA9IHJybV9yZWR1Y2VkX3RyYWluLG1ldGhvZD0iU1ZEIixwYXJhbWV0ZXI9bGlzdChub3JtYWxpemUgPSAiWi1zY29yZSIsaz0zMCkpDQptb2RlbF9TVkRfNDAgPC0gUmVjb21tZW5kZXIoZGF0YSA9IHJybV9yZWR1Y2VkX3RyYWluLG1ldGhvZD0iU1ZEIixwYXJhbWV0ZXI9bGlzdChub3JtYWxpemUgPSAiWi1zY29yZSIsaz00MCkpDQptb2RlbF9TVkRfNTAgPC0gUmVjb21tZW5kZXIoZGF0YSA9IHJybV9yZWR1Y2VkX3RyYWluLG1ldGhvZD0iU1ZEIixwYXJhbWV0ZXI9bGlzdChub3JtYWxpemUgPSAiWi1zY29yZSIsaz01MCkpDQoNCiMgZXZhbHVhdGUgcmVjb21tZW5kYXRpb25zIG9uICJ1bmtub3duIiByYXRpbmdzDQphY2NfU1ZEXzEwIDwtIGNhbGNQcmVkaWN0aW9uQWNjdXJhY3kocHJlZGljdChvYmplY3QgPSBtb2RlbF9TVkRfMTAsIG5ld2RhdGEgPSBycm1fcmVkdWNlZF9rbm93biwgbiA9IDE1LHR5cGU9InRvcE5MaXN0IikscnJtX3JlZHVjZWRfdW5rbm93bixnaXZlbj0yMCxnb29kUmF0aW5nID0gNCkNCmFjY19TVkRfMjAgPC0gY2FsY1ByZWRpY3Rpb25BY2N1cmFjeShwcmVkaWN0KG9iamVjdCA9IG1vZGVsX1NWRF8yMCwgbmV3ZGF0YSA9IHJybV9yZWR1Y2VkX2tub3duLCBuID0gMTUsdHlwZT0idG9wTkxpc3QiKSxycm1fcmVkdWNlZF91bmtub3duLGdpdmVuPTIwLGdvb2RSYXRpbmcgPSA0KQ0KYWNjX1NWRF8zMCA8LSBjYWxjUHJlZGljdGlvbkFjY3VyYWN5KHByZWRpY3Qob2JqZWN0ID0gbW9kZWxfU1ZEXzMwLCBuZXdkYXRhID0gcnJtX3JlZHVjZWRfa25vd24sIG4gPSAxNSx0eXBlPSJ0b3BOTGlzdCIpLHJybV9yZWR1Y2VkX3Vua25vd24sZ2l2ZW49MjAsZ29vZFJhdGluZyA9IDQpDQphY2NfU1ZEXzQwIDwtIGNhbGNQcmVkaWN0aW9uQWNjdXJhY3kocHJlZGljdChvYmplY3QgPSBtb2RlbF9TVkRfNDAsIG5ld2RhdGEgPSBycm1fcmVkdWNlZF9rbm93biwgbiA9IDE1LHR5cGU9InRvcE5MaXN0IikscnJtX3JlZHVjZWRfdW5rbm93bixnaXZlbj0yMCxnb29kUmF0aW5nID0gNCkNCmFjY19TVkRfNTAgPC0gY2FsY1ByZWRpY3Rpb25BY2N1cmFjeShwcmVkaWN0KG9iamVjdCA9IG1vZGVsX1NWRF81MCwgbmV3ZGF0YSA9IHJybV9yZWR1Y2VkX2tub3duLCBuID0gMTUsdHlwZT0idG9wTkxpc3QiKSxycm1fcmVkdWNlZF91bmtub3duLGdpdmVuPTIwLGdvb2RSYXRpbmcgPSA0KQ0KDQphY2NfSUJDRl90b3AxNSA8LSBjYWxjUHJlZGljdGlvbkFjY3VyYWN5KHByZWRpY3Qob2JqZWN0ID0gbW9kZWxfSUJDRiwgbmV3ZGF0YSA9IHJybV9yZWR1Y2VkX2tub3duLCBuID0gMTUsdHlwZT0idG9wTkxpc3QiKSxycm1fcmVkdWNlZF91bmtub3duLGdpdmVuPTIwLGdvb2RSYXRpbmcgPSA0KQ0KDQphY2NfU1ZEX0lCIDwtIHJiaW5kKGFjY19TVkRfMTAsYWNjX1NWRF8yMCxhY2NfU1ZEXzMwLGFjY19TVkRfNDAsYWNjX1NWRF81MCxhY2NfSUJDRl90b3AxNSkNCnJvd25hbWVzKGFjY19TVkRfSUIpIDwtIGMoIlNWRF9rXzEwIiwiU1ZEX2tfMjAiLCJTVkRfa18zMCIsIlNWRF9rXzQwIiwiU1ZEX2tfNTAiLCJJQkNGX2Nvc19rXzMwIikNCmFjY19TVkRfSUINCmBgYA0KIyMjIFRoZSBtb2RlbCB3aXRoIFNWRCBhbmQgMTAgbmVpZ2hib3JzIGhhdmUgdGhlIGJlc3QgcHJlY2lzaW9uIGFuZCByZWNhbGwuIA0KIyMjIFNWRCBrPTEwID4gU1ZEIGs9MjAgPiBTVkQgaz00MCA+IFNWRCBrPTMwID4gSUJDRiBjb3NpbmUgaz0zMCA+IFNWRCBrPTUwDQoNCg0KOCBXYWhsIGRlcyBvcHRpbWFsZW4gUmVjb21tZW5kZXJzIEF1ZmdhYmU6IA0KQmVzdGltbWUgYXVzIDUgdW50ZXJzY2hpZWRsaWNoZW4gTW9kZWxsZW4gZGFzIGhpbnNpY2h0bGljaCBUb3AtTiBFbXBmZWhsdW5nZW4gYmVzdGUgTW9kZWxsLiANCkJlZ3LDvG5kZSBkZWluZSBNb2RlbGx3YWhsZW4gYXVmZ3J1bmQgZGVyIGJpc2hlciBnZW1hY2h0ZW4gRXJrZW5udG5pc3NlIHVuZCB2ZXJ3ZW5kZSBhbHMgNi4gTW9kZWxsIGVpbmVuIFRvcC1Nb3ZpZSBSZWNvbW1lbmRlciAoQmFzaXM6IHJlZHV6aWVydGVyIERhdGVuc2F0eikuDQoNCg0KOC4xIFZlcndlbmRlIGbDvHIgZGllIEV2YWx1aWVydW5nIDEwLWZhY2hlIEtyZXV6dmFsaWRpZXJ1bmcNCg0KYGBge3J9DQojY3JlYXRlIDEwLWZvbGQgY3Jvc3MgdmFsaWRhdGlvbiBzY2hlbWUNCnNldC5zZWVkKDY5NTQpDQpzY2hlbWUgPC0gZXZhbHVhdGlvblNjaGVtZShycm1fcmVkdWNlZCwgbWV0aG9kPSJjcm9zcyIsIGs9MTAsIGdpdmVuPTIwLCBnb29kUmF0aW5nPTQpDQoNCiMgZXZhbHVhdGUgd2l0aCBkaWZmZXJlbnQgbWV0aG9kcw0KY3ZfSUJDRiA8LSBldmFsdWF0ZShzY2hlbWUsIG1ldGhvZD0iSUJDRiIsIHR5cGUgPSAidG9wTkxpc3QiLHBhcmFtZXRlcj1saXN0KG5vcm1hbGl6ZSA9ICJaLXNjb3JlIixtZXRob2Q9ImNvc2luZSIsaz0zMCksbj0xNSkNCmN2X1VCQ0YgPC0gZXZhbHVhdGUoc2NoZW1lLCBtZXRob2Q9IlVCQ0YiLCB0eXBlID0gInRvcE5MaXN0IixwYXJhbWV0ZXI9bGlzdChub3JtYWxpemUgPSAiWi1zY29yZSIsbWV0aG9kPSJjb3NpbmUiLG5uPTMwKSxuPTE1KQ0KY3ZfU1ZEIDwtIGV2YWx1YXRlKHNjaGVtZSwgbWV0aG9kPSJTVkQiLCB0eXBlID0gInRvcE5MaXN0IixwYXJhbWV0ZXI9bGlzdChub3JtYWxpemUgPSAiWi1zY29yZSIsaz0zMCksbj0xNSkNCmN2X1JBTkRPTSA8LSBldmFsdWF0ZShzY2hlbWUsbWV0aG9kPSJSQU5ET00iLHR5cGU9InRvcE5MaXN0IixuPTE1KQ0KY3ZfUE9QIDwtIGV2YWx1YXRlKHNjaGVtZSwgbWV0aG9kPSJQT1BVTEFSIiwgdHlwZSA9ICJ0b3BOTGlzdCIscGFyYW1ldGVyPWxpc3Qobm9ybWFsaXplID0gIlotc2NvcmUiKSxuPTE1KQ0KDQojIGdldCB0aGUgYXZlcmFnZWQgZXZhbHVhdGlvbiByZXN1bHRzDQpSZXN1bHRfODEgPC0gcmJpbmQoYXZnKGN2X0lCQ0YpLGF2Zyhjdl9VQkNGKSxhdmcoY3ZfU1ZEKSxhdmcoY3ZfUkFORE9NKSxhdmcoY3ZfUE9QKSkNCnJvd25hbWVzKFJlc3VsdF84MSkgPC0gYygiSUJDRiIsIlVCQ0YiLCJTVkQiLCJSQU5ET00iLCJQT1BVTEFSIikNClJlc3VsdF84MQ0KDQpgYGANCiMjIyBUaGUgbW9kZWwgd2l0aCBwb3B1bGFyIG1ldGhvZCBoYXMgdGhlIGJlc3QgcHJlY2lzaW9uIGFuZCByZWNhbGwuDQojIyMgUG9wdWxhciA+IElCQ0YgfiBTVkQgPiBSQU5ET00gPiBVQkNGDQoNCg0KOC4yIEJlZ3LDvG5kZSBkZWluZSBXYWhsIGRlciBQZXJmb3JtYW5jZSBNZXRyaWssDQoNCiMjIyBIaWdoZXIgcHJlY2lzaW9uIG1lYW5zIHRoYXQgYW4gYWxnb3JpdGhtIHJldHVybnMgbW9yZSByZWxldmFudCByZXN1bHRzIHRoYW4gaXJyZWxldmFudCBvbmVzLCBhbmQgaGlnaCByZWNhbGwgbWVhbnMgdGhhdCBhbiBhbGdvcml0aG0gcmV0dXJucyBtb3N0IG9mIHRoZSByZWxldmFudCByZXN1bHRzICh3aGV0aGVyIG9yIG5vdCBpcnJlbGV2YW50IG9uZXMgYXJlIGFsc28gcmV0dXJuZWQpLg0KDQojIyMgQSBwZXJmZWN0IHByZWNpc2lvbiBzY29yZSBvZiAxLjAgbWVhbnMgdGhhdCBldmVyeSByZXN1bHQgcmV0cmlldmVkIHdhcyByZWxldmFudCAoYnV0IHNheXMgbm90aGluZyBhYm91dCB3aGV0aGVyIGFsbCByZWxldmFudCBkb2N1bWVudHMgd2VyZSByZXRyaWV2ZWQpIHdoZXJlYXMgYSBwZXJmZWN0IHJlY2FsbCBzY29yZSBvZiAxLjAgbWVhbnMgdGhhdCBhbGwgcmVsZXZhbnQgZG9jdW1lbnRzIHdlcmUgcmV0cmlldmVkIGJ5IHRoZSBzZWFyY2ggKGJ1dCBzYXlzIG5vdGhpbmcgYWJvdXQgaG93IG1hbnkgaXJyZWxldmFudCBkb2N1bWVudHMgd2VyZSBhbHNvIHJldHJpZXZlZCkNCg0KIyMjIFRoZSBtb2RlbCBQb3B1bGFyIHJldHVybnMgdGhlIGhpZ2hlc3Qgc2NvcmUgb2YgYm90aCBwcmVjaXNpb24gYW5kIHJlY2FsbC4gDQojIyMgUG9wdWxhciA+IFNWRCB+IElCQ0YgPiBSQU5ET00gPiBVQkNGDQoNCg0KOC4zIEFuYWx5c2llcmUgZGFzIGJlc3RlIE1vZGVsbCBmw7xyIFRvcC1OIFJlY29tbWVuZGF0aW9ucyBtaXQgTiBnbGVpY2ggMTAsIDE1LCAyMCwgMjUgdW5kIDMwLA0KDQpgYGB7cn0NClBPUF9yZXN1bHRzIDwtIGV2YWx1YXRlKHNjaGVtZSwgbWV0aG9kPSJQT1BVTEFSIiwgdHlwZSA9ICJ0b3BOTGlzdCIscGFyYW1ldGVyPWxpc3Qobm9ybWFsaXplID0gIlotc2NvcmUiKSxuPWMoMTAsMTUsMjAsMjUsMzApKQ0KYXZnX1BPUF9yZXN1bHRzIDwtIGF2ZyhQT1BfcmVzdWx0cykNCmF2Z19QT1BfcmVzdWx0cw0KYGBgDQojIyMgV2hlbiBJIGluY3JlYXNlIHRoZSBOLCB0aGUgInJlY2FsbCIgaXMgZ2V0dGluZyBiZXR0ZXIgKGxhcmdlciB2YWx1ZSksIGJ1dCB0aGUgInByZWNpc2lvbiIgaXMgZ2V0dGluZyB3b3JzZSAoc21hbGxlciB2YWx1ZSkuDQoNCg0KOC40IE9wdGltaWVyZSBkZWluIGJlc3RlcyBNb2RlbGwgaGluc2ljaHRsaWNoIEh5cGVycGFyYW1ldGVyLg0KSGlud2VpczogVmVyd2VuZGUgZsO8ciBkZW4gVG9wLU1vdmllIFJlY29tbWVuZGVyIGRpZSBGaWxtZSBtaXQgZGVuIGjDtmNoc3RlbiBEdXJjaHNjaG5pdHRzcmF0aW5ncy4NCg0KYGBge3J9DQojIGZpbG1zIHdpdGggb25seSB0aGUgaGlnaGVzdCBhdmVyYWdlIHJhdGluZ3MgKHJhdGluZ3MgPiAzKQ0KZGZfdG9wX2F2ZyA8LSBhcy5kYXRhLmZyYW1lKHQoZGZfcmVkdWNlZCkpDQpkZl90b3BfYXZnIDwtIGRmX3RvcF9hdmcgJT4lIG11dGF0ZShhdmdfcmF0aW5nID0gcm93TWVhbnMoZGZfdG9wX2F2ZyxuYS5ybT1UUlVFLGRpbXM9MSkpJT4lIGFycmFuZ2UoZGVzYyhhdmdfcmF0aW5nKSklPiUgZmlsdGVyKGF2Z19yYXRpbmc+MykgJT4lIHNlbGVjdCgtYXZnX3JhdGluZykNCnJybV90b3BfYXZnIDwtIGFzKHQoZGZfdG9wX2F2ZyksInJlYWxSYXRpbmdNYXRyaXgiKQ0KDQoNCnNldC5zZWVkKDg0Njk1NCkNCnNjaGVtZV90b3BfYXZnIDwtIGV2YWx1YXRpb25TY2hlbWUocnJtX3RvcF9hdmcsIG1ldGhvZD0iY3Jvc3MiLCBrPTEwLCBnaXZlbj0yMCwgZ29vZFJhdGluZz00KQ0KDQojIHRoZSBtb2RlbCBQb3B1bGFyIGhhcyBvbmx5IG9uZSBwYXJhbWV0ZXI6IG5vcm1hbGl6ZS4gSGVyZSBJIHdpbGwgY29tcGFyZSB0d28gbm9ybWFsaXphdGlvbiBtZXRob2RzOiB6LXNjb3JlIGFuZCBjZW50ZXINClBPUF90b3BfYXZnX3ogPC0gYXZnKGV2YWx1YXRlKHNjaGVtZV90b3BfYXZnLCBtZXRob2Q9IlBPUFVMQVIiLCB0eXBlID0gInRvcE5MaXN0IixwYXJhbWV0ZXI9bGlzdChub3JtYWxpemUgPSAiWi1zY29yZSIpLG49YygxMCwxNSwyMCwyNSwzMCkpKQ0KDQpQT1BfdG9wX2F2Z19jZW50ZXIgPC0gYXZnKGV2YWx1YXRlKHNjaGVtZV90b3BfYXZnLCBtZXRob2Q9IlBPUFVMQVIiLCB0eXBlID0gInRvcE5MaXN0IixwYXJhbWV0ZXI9bGlzdChub3JtYWxpemUgPSAiY2VudGVyIiksbj1jKDEwLDE1LDIwLDI1LDMwKSkpDQoNCmRpZmZfel9jZW50ZXIgPC0gY2JpbmQoKFBPUF90b3BfYXZnX3ogLSBQT1BfdG9wX2F2Z19jZW50ZXIpWyw2OjddLFBPUF90b3BfYXZnX3pbLDEwXSkgDQpQT1BfdG9wX2F2Z196OyBQT1BfdG9wX2F2Z19jZW50ZXI7IGRpZmZfel9jZW50ZXINCmBgYA0KIyMjIEhlcmUgSSB0cmllZCB0byBvcHRpbWl6ZSB0aGUgcG9wdWxhciBtb2RlbCB0aHJvdWdoIHRoZSBub3JtYWxpemF0aW9uIHBhcmFtZXRlci4gVGhlIHR3byBub3JtYWxpYXphdGlvbiBtZXRob2RzIHotc2NvcmUgYW5kIGNlbnRlciBoYXZlIHZlcnkgc2ltaWxpYXIgcGVyZm9ybWFuY2Ugb24gdGhlIHByZWNpc2lvbiBhbmQgcmVjYWxsLiBUaGUgbW9kZWxzIHdpdGggei1zY29yZSBoYXMgc2xpZ2h0bHkgYmV0dGVyIHBlcmZvcm1hbmNlIHRoYW4gdGhlIGNlbnRlciBub3JtYWxpemF0aW9uIHdpdGggbiA9IDEwLCAxNSwgMjUsIDMwLiBUaGUgbW9kZWwgd2l0aCBjZW50ZXIgbm9ybWFsaXphdGlvbiBwZXJmb3JtZWQgYSBiaXQgYmV0dGVyIHdpdGggbiA9IDIwLiANCg0KDQo5IEltcGxlbWVudGllcnVuZyDDhGhubGljaGtlaXRzbWF0cml4DQoNCkF1ZmdhYmUgRElZOiBJbXBsZW1lbnRpZXJlIGVpbmUgRnVua3Rpb24genVyIGVmZml6aWVudGVuIEJlcmVjaG51bmcgdm9uIHNwYXJzZW4gw4RobmxpY2hrZWl0c21hdHJpemVuIGbDvHIgSUJDRiBSUyB1bmQgYW5hbHlzaWVyZSBkaWUgUmVzdWx0YXRlIGbDvHIgMTAwIHp1ZsOkbGxpZyBnZXfDpGhsdGUgRmlsbWUuDQoNCjkuMSBJbXBsZW1lbnRpZXJlIGVpbmUgRnVua3Rpb24sIHVtIGbDvHIgb3JkaW5hbGUgUmF0aW5ncyBlZmZpemllbnQgZGllIENvc2luZSBTaW1pbGFyaXR5IHp1IGJlcmVjaG5lbiwNCg0KYGBge3J9DQpjb3Nfc2ltaWxhcml0eSA8LSBmdW5jdGlvbihteCl7DQogICAgbiA8LSBkaW0obXgpWzJdDQogICAgbXhfMCA8LSBteA0KICAgIG14XzBbaXMubmEobXhfMCldIDwtIDANCiAgICBzaW1fbXggPC0gbWF0cml4KDE6bl4yLCBucm93ID0gbikNCiAgICBmb3IoaSBpbiAxOm4pew0KICAgICAgZm9yKGogaW4gMTpuKXsNCiAgICAgICAgIA0KICAgICAgICBudW1lcmF0b3IgPC0gdChteF8wWyxpXSkgJSolIG14XzBbLGpdDQogICAgICAgIGRlbm9taW5hdG9yIDwtIHNxcnQoc3VtKG14XzBbLGldXjIpKSpzcXJ0KHN1bShteF8wWyxqXV4yKSkNCiAgICAgICAgc2ltX214W2ksal0gPC0gbnVtZXJhdG9yL2Rlbm9taW5hdG9yDQogICAgICB9DQogICAgfQ0KICAgIHJldHVybihzaW1fbXgpDQp9DQoNCmNvc19zaW1fcmVkdWNlZF8xIDwtIGNvc19zaW1pbGFyaXR5KGRmX3JlZHVjZWQpDQoNCmBgYA0KDQoNCjkuMiBJbXBsZW1lbnRpZXJlIGVpbmUgRnVua3Rpb24sIHVtIGbDvHIgYmluw6RyZSBSYXRpbmdzIGVmZml6aWVudCBkaWUgSmFjY2FyZCBTaW1pbGFyaXR5IHp1IGJlcmVjaG5lbiwNCg0KDQpgYGB7cn0NCkphY2Nfc2ltaWxhcml0eSA8LSBmdW5jdGlvbihteCl7DQogICAgbXhfYmkgPC0gbXgNCiAgICBteF9iaVtteF9iaSA8PSAzXSA8LSAwIA0KICAgIG14X2JpW2lzLm5hKG14X2JpKV0gPC0gMCAjIHRoZSBOQSBhbmQgcmF0aW5ncyA8PSAzIGFsbCBjb252ZXJ0ZWQgYXMgMA0KICAgIG14X2JpW214X2JpID4gM10gPC0gMSAjIHRoZSByYXRpbmdzID4gMyAod2hpY2ggc2hvd3MgYSBwcmVmZXJlbmNlKSBjb252ZXJ0ZWQgYXMgMQ0KICAgIA0KICAgIG4gPC0gZGltKG14X2JpKVsyXQ0KICAgIA0KICAgIHNpbV9teCA8LSBtYXRyaXgoMTpuXjIsIG5yb3cgPSBuKSAjIGNyZWF0ZSBhIG1hdHJpeCB3aXRoIGRpbWVudGlvbiBvZiBuIHggbiBmb3Igc2ltaWxhcml0eSANCiAgICBmb3IoaSBpbiAxOm4pew0KICAgICAgZm9yKGogaW4gMTpuKXsNCiAgICAgICAgZGlmZiA8LSBzdW0oYWJzKG14X2JpWyxpXSAtIG14X2JpWyxqXSkpICMgdGhlIHN1bSBvZiBhYnNvbHV0ZSBkaWZmZXJlbmNlIGJldHdlZW4gdHdvIHZlY3RvcnM6IHNpbmNlIHRoZSBwYWlycyBhcmUgZWl0aGVyIHNhbWUgb3Igd2l0aCB0aGUgZGlmZmVyZW5jZSBvZiAxLCB0aGlzIG1lYW5zIHRoZSByZXN1bHQgc2hvd3MgYWxzbyBob3cgbWFueSBwYWlycyBhcmUgZGlmZmVyZW50Lg0KICAgICAgICBzaW1fbXhbaSxqXSA8LSAxIC0gZGlmZi9uIA0KICAgICAgfQ0KICAgIH0NCiAgICByZXR1cm4oc2ltX214KQ0KICB9DQoNCkphY2Nfc2ltX3JlZHVjZWQgPC0gSmFjY19zaW1pbGFyaXR5KGRmX3JlZHVjZWQpICAjIGEgNzAwIHggNzAwIHNpbWlsYXJpdHkgbWF0cml4DQpgYGANCg0KDQoNCjkuMyBWZXJnbGVpY2hlIGRlaW5lIEltcGxlbWVudGllcnVuZyBkZXIgQ29zaW5lLWJhc2llcnRlbiDDhGhubGljaGtlaXRzbWF0cml4IGbDvHIgb3JkaW5hbGUgS3VuZGVucmF0aW5ncyBtaXQgZGVyIGtvcnJlc3BvbmRpZXJlbmRlbiB2aWEgT3BlbiBTb3VyY2UgUGFrZXRlbiBlcnpldWd0ZW4gw4RobmxpY2hrZWl0c21hdHJpeCwNCg0KYGBge3J9DQpteF9yZWR1Y2VkXzAgPC0gbXhfcmVkdWNlZA0KbXhfcmVkdWNlZF8wW2lzLm5hKG14X3JlZHVjZWRfMCldPC0wICAjIHJlcGxhY2UgTkEgYXMgMA0KY29zX3NpbV9yZWR1Y2VkXzIgPC0gYXMubWF0cml4KHNpbWlsYXJpdHkoYXMobXhfcmVkdWNlZF8wLCJyZWFsUmF0aW5nTWF0cml4IiksIG1ldGhvZCA9ICJjb3NpbmUiLCB3aGljaCA9ICJpdGVtcyIpKSAjIGNhbGN1bGF0ZSB0aGUgY29zaW5lIHNpbWlsYXJpdHkgbWF0cml4IGJ5IG9wZW4gc291cmNlIHBhY2thZ2UNCg0KIyBTaW5jZSB0aGUgY29zIHNpbWlsYXJpdHkgbWF0cml4IGJ5IHRoaXMgbWV0aG9kIHVzZSAwIGZvciBhbGwgdGhlIGRpYWdvbmFsIGVsZW1lbnRzLCB3aGVyZSBhbGwgYXJlIDEgYnkgdGhlIHVwcGVyIGZ1bmN0aW9uIHRvIHJlbW92ZSB0aGlzIGVmZmVjdCwgaGVyZSBpIHdpbGwgcmVmaWxsIHRoZSBkaWFnb25hbCB3aXRoIDENCmRpYWcoY29zX3NpbV9yZWR1Y2VkXzIpPC0xDQoNCmNvbXBhcmVfdHdvX2Nvc19zaW1fbWV0aG9kcyA8LSBhbGwuZXF1YWwoY29zX3NpbV9yZWR1Y2VkXzEsIGNvc19zaW1fcmVkdWNlZF8yLCB0b2xlcmFuY2UgPSAxZS0xMCxjaGVjay5hdHRyaWJ1dGVzID0gRkFMU0UpDQpjb21wYXJlX3R3b19jb3Nfc2ltX21ldGhvZHMNCmBgYA0KIyMjIFRoZSBjb3NpbmUgc2ltaWxhcml0eSBtYXRyaWNlcyBieSB0d28gZGlmZmVyZW50IG1ldGhvZHMgYXJlIGVxdWFsICh3aXRoIHRvbGVyYW5jZSBvZiAxZS0xMCkuDQoNCg0KDQo5LjQgVmVyZ2xlaWNoZSB1bmQgZGlza3V0aWVyZSBkaWUgVW50ZXJzY2hpZWRlIGRlaW5lciBtaXR0ZWxzIENvc2luZSBTaW1pbGFyaXR5IGVyemV1Z3RlbiDDhGhubGljaGtlaXRzbWF0cml6ZW4gZsO8ciBvcmRpbmFsZSB1bmQgbm9ybWllcnRlIEt1bmRlbnJhdGluZ3MgbWl0IGRlciBKYWNjYXJkLWJhc2llcnRlbiDDhGhubGljaGtlaXRzbWF0cml4Lg0KDQpgYGB7cn0NCmNvbXBhcmVfY29zX0phY2MgPC0gYWxsLmVxdWFsKGNvc19zaW1fcmVkdWNlZF8xLEphY2Nfc2ltX3JlZHVjZWQsdG9sZXJhbmNlID0gMWUtMyxjaGVjay5hdHRyaWJ1dGVzID0gRkFMU0UpDQpjb21wYXJlX2Nvc19KYWNjDQpgYGANCiMjIyBUaGUgbWVhbiByZWxhdGl2ZSBkaWZmZXJlbmNlIGJldHdlZW4gY29zaW5lIHNpbWlsYXJpdHkgYW5kIGphY2NhcmQgc2ltaWxhcml0eSBpcyAyLjQ4Lg0KIyMjIEphY2NhcmQgc2ltaWxhcml0eSB0YWtlcyBvbmx5IHRoZSB1bmlxdWUgc2V0IG9mIGl0ZW1zLiBUaGUgY29zaW5lIHNpbWlsYXJpdHkgdGFrZXMgdGhlIHRvdGFsIGxlbmd0aCBvZiB0aGUgdmVjdG9ycy4NCg0KDQoNCjEwIEltcGxlbWVudGllcnVuZyBUb3AtTiBNZXRyaWtlbg0KDQpBdWZnYWJlIERJWTogSW1wbGVtZW50aWVyZSBGdW5rdGlvbmVuIGbDvHIgZGllIEJldXJ0ZWlsdW5nIGRlciBUb3AtTiBNZXRyaWtlbiBQcmVjaXNpb24gdW5kIFJlY2FsbCBzb3dpZSBmw7xyIGFsbGUgS3VuZGVuIGRlciBJdGVtLXNwYWNlIENvdmVyYWdlIHVuZCBOb3ZlbHR5IHVuZCB0ZXN0ZSBkaWVzZSBtaXQgSUJDRiBSZWNvbW1lbmRhdGlvbnMgKEJhc2lzOiByZWR1emllcnRlciBEYXRlbnNhdHo7IE4gPSA1LCAxMCwgMTUsIDIwLCAyNSwgMzApDQoNCg0KMTAuMSBJbXBsZW1lbnRpZXJlIGVpbmUgRnVua3Rpb24sIHVtIGF1cyBUb3AtTiBMaXN0ZW4gZsO8ciBhbGxlIEt1bmRlbiBkaWUgSXRlbS1zcGFjZSBDb3ZlcmFnZUBOIHVuZCBOb3ZlbHR5QE4gZWluZXMgUmVjb21tZW5kZXJzIHp1IGJldXJ0ZWlsZW4gdW5kIHRlc3RlIGRpZXNlLg0KDQoNCmBgYHtyfQ0KY2FsY190b3BuX21ldHJpY3MgPC0gZnVuY3Rpb24obXgsc3BsaXRfcmF0aW8sTil7ICAjIG14OiBVX0kgZGF0YTsgc3BsaXRfcmF0aW86dHJhaW4gZGF0YSBwcm9wb3J0aW9uOyBuOiBUb3AtTg0KICBycm0gPC0gYXMobXgsInJlYWxSYXRpbmdNYXRyaXgiKQ0KICAjIHNwbGl0IHRyYWluLCB0ZXN0LWtub3duLCB0ZXN0X3Vua25vd24gZGF0YQ0KICB0cmFpbl90ZXN0IDwtIGV2YWx1YXRpb25TY2hlbWUocnJtLCBtZXRob2Q9InNwbGl0IiwgdHJhaW49c3BsaXRfcmF0aW8sIGs9MSwgZ2l2ZW49MjAsZ29vZFJhdGluZz00KQ0KICBycm1fdHJhaW4gPC0gZ2V0RGF0YSh0cmFpbl90ZXN0LCJ0cmFpbiIpDQogIHJybV9rbm93biA8LSBnZXREYXRhKHRyYWluX3Rlc3QsImtub3duIikgDQogIHJybV91bmtub3duIDwtIGdldERhdGEodHJhaW5fdGVzdCwidW5rbm93biIpDQogICMgSUJDRiBtb2RlbA0KICBtb2RlbF9JQkNGIDwtUmVjb21tZW5kZXIoZGF0YSA9IHJybV90cmFpbixtZXRob2Q9IklCQ0YiLHBhcmFtZXRlcj1saXN0KG5vcm1hbGl6ZSA9ICJaLXNjb3JlIixtZXRob2Q9IkNvc2luZSIsaz0xMCkpDQogICMgcHJlZGljdCBUb3AtTiByZWNvbW1lbmRhdGlvbiBsaXN0DQogIHByZWRfSUJDRiA8LSBwcmVkaWN0KG9iamVjdCA9IG1vZGVsX0lCQ0YsIG5ld2RhdGEgPSBycm1fa25vd24sIG4gPSBOLHR5cGU9InRvcE5MaXN0IikNCiAgDQogICMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIw0KICANCiAgIyMjIGFjY3VyYWN5OiBldmFsdWF0ZSB0aGUgcmVjb21tZW5kYXRpb25zIG9uICJ1bmtub3duIiByYXRpbmdzIHdpdGggbWV0cmljcyBwcmVjaXNpb24gYW5kIHJlY2FsbA0KICBhY2NfSUJDRiA8LSBjYWxjUHJlZGljdGlvbkFjY3VyYWN5KHByZWRpY3Qob2JqZWN0ID0gbW9kZWxfSUJDRiwgbmV3ZGF0YSA9IHJybV9rbm93biwgbiA9IE4sdHlwZT0idG9wTkxpc3QiKSxycm1fdW5rbm93bixnaXZlbj0yMCxnb29kUmF0aW5nID0gNCkNCiAgDQogIGFjY19JQkNGIDwtIHQoYXMuZGF0YS5mcmFtZShhY2NfSUJDRikpDQogIHJvd25hbWVzKGFjY19JQkNGKSA8LSBOVUxMDQogIA0KICAjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMNCiAgDQogICMjIyBpdGVtLXNwYWNlIGNvdmVyYWdlOiBob3cgbWFueSBwZXJjZW50YWdlIG9mIGZpbG1zKGZyb20gdGhlIHRyYWluIGRhdGEpIGFyZSBpbiB0aGUgdG9wLW4gcmVjb21tZW5kYXRpb24gbGlzdHMNCiAgIyB0b3AgbiBsaXN0cyBmb3IgZXZlcnkgdXNlcg0KICAgDQogIFRPUF9OX2xpc3QgPC0gc2FwcGx5KHByZWRfSUJDRkBpdGVtcywgZnVuY3Rpb24oeCkge2NvbG5hbWVzKGFzKHJybV9rbm93biwibWF0cml4IikpW3hdfSkgDQogICMgdW5pcXVlIHByZWRpY3RlZCBmaWxtIGxpc3Qgb2YgYWxsIHRlc3QgdXNlcnMgDQogIHVuaXFfZmlsbV90ZXN0IDwtIHJlc2hhcGUyOjptZWx0KGFzKFRPUF9OX2xpc3QsIm1hdHJpeCIpKSAlPiUgcmVuYW1lKFVzZXJJRCA9IFZhcjIsIHJhbmsgPSBWYXIxLCBGaWxtX25hbWUgPSB2YWx1ZSklPiVkaXN0aW5jdChGaWxtX25hbWUpICAgIyB1bmlxdWUgZmlsbSBsaXN0IHJlY29tbWVuZGVkIGluIHRlc3QgZGF0YQ0KICANCiAgIyB1bmlxdWUgZmlsbSBsaXN0IG9mIHRoZSB0cmFpbiBkYXRhDQogIHVuaXFfZmlsbV90cmFpbiA8LSBhcy5kYXRhLmZyYW1lKHQobXgpKQ0KICB1bmlxX2ZpbG1fdHJhaW4kY250IDwtIHJvd1N1bXMoIWlzLm5hKHVuaXFfZmlsbV90cmFpbikpICMgY291bnQgbm90IE5BIGZvciBlYWNoIGZpbG0NCiAgdW5pcV9maWxtX3RyYWluIDwtIHVuaXFfZmlsbV90cmFpbiAlPiUgZmlsdGVyKGNudD4wKSAgIyByZW1vdmUgdGhlIGZpbG0gd2l0aG91dCBhbnkgcmF0aW5ncw0KICANCiAgIyBjYWxjdWxhdGUgdGhlIGl0ZW0tc3BhY2UgY292ZXJhZ2UNCiAgY292ZXJhZ2UgPC0gZGltKHVuaXFfZmlsbV90ZXN0KVsxXSAvIGRpbSh1bmlxX2ZpbG1fdHJhaW4pWzFdICMgdGhlIGNvdmVyYWdlDQogIGNvdmVyYWdlIDwtIGFzLmRhdGEuZnJhbWUoY292ZXJhZ2UpDQogIGNvbG5hbWVzKGNvdmVyYWdlKSA8LSAiY292ZXJhZ2UiDQogIA0KICAjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMNCiAgDQogICMjIyBub3ZlbHR5IGZvciBhIGdpdmVuIHVzZXI6IHJhdGlvIG9mIHVua25vd24gaXRlbXMgaW4gdGhlIHRvcC1uIGxpc3QgDQogIG5vdmVsdHlfdGFibGUgPC0gZGF0YS5mcmFtZSgpICMgYW4gZW1wdHkgZGF0YWZyYW1lLCB3aWxsIGJlIGZpbGxlZCB3aXRoIG5vdmVsdHkgdmFsdWVzDQogIGRmIDwtIGFzLmRhdGEuZnJhbWUobXgpDQogIHByZWRfSUJDRl9hbGxfdXNlciA8LSBwcmVkaWN0KG9iamVjdCA9IG1vZGVsX0lCQ0YsIG5ld2RhdGEgPSBycm0sIG4gPSBOLHR5cGU9InRvcE5MaXN0IikgIyBwcmVkaWN0IGZvciBhbGwgdXNlcnMNCiAgVE9QX05fbGlzdF9hbGxfdXNlciA8LSBzYXBwbHkocHJlZF9JQkNGX2FsbF91c2VyQGl0ZW1zLCBmdW5jdGlvbih4KSB7Y29sbmFtZXMobXgpW3hdfSkgIyB0b3AtbiBsaXN0IGZvciBhbGwgdXNlcnMNCiAgIyBkZl8xOiByZXBsYWNlIHRoZSBub3QgTkEgdmFsdWVzIHRvIHRoZSBjb3JyZXNwb25kaW5nIGNvbHVtbiBuYW1lIA0KICBmb3IoaSBpbiAxOmRpbShteClbMV0pew0KICAgIGRmX2kgPC0gYXMuZGF0YS5mcmFtZSh0KG14KSkjICANCiAgICBkZl9pJEZpbG0gPC0gY29sbmFtZXMobXgpDQogICAgZGZfaSA8LSBkZl9pWyxjKGksKGRpbShteClbMV0rMSkpXSAlPiUgZmlsdGVyKGNvbXBsZXRlLmNhc2VzKC4pKSAjIGxpc3Qgb2YgdXNlci1pIHJhdGVkIGZpbG1zDQogICAgZGZfaSRGaWxtIDwtIHJvd25hbWVzKGRmX2kpICMgYWRkIGEgbmV3IGNvbHVtbiB3aXRoIHRoZSBzYW1lIGNvbnRlbnQgb2Ygcm93bmFtZXMNCiAgICANCiAgICBkZl90b3BfbiA8LSBhcy5kYXRhLmZyYW1lKFRPUF9OX2xpc3RfYWxsX3VzZXJbLGldKSAgICMgdG9wLW4gbGlzdCBvZiB1c2VyLWkNCiAgICBjb2xuYW1lcyhkZl90b3BfbikgPC0gIkZpbG0iDQogICAgDQogICAgZGZfY3Jvc3MgPC0gaW5uZXJfam9pbihkZl9pLCBkZl90b3BfbiwgYnk9IkZpbG0iKSAgIyBpbm5lciBqb2luIHRoZSB0d28gZGF0YXNldCwgd2UgZ2V0IHRoZSByYXRlZCBpdGVtcyBpbiB0aGUgdG9wLW4gbGlzdA0KICAgIA0KICAgIG5vdmVsdHkgPC0gMSAtIGRpbShkZl9jcm9zcylbMV0vTiAgIyBub3ZlbHR5IHZhbHVlIG9mIHVzZXItaQ0KICAgIG5vdmVsdHlfdGFibGUgPC0gcmJpbmQobm92ZWx0eV90YWJsZSwgbm92ZWx0eSkNCiAgfQ0KICANCiAgbm92ZWx0eV90YWJsZSRVc2VySUQgPC0gcm93bmFtZXMobXgpDQogIGNvbG5hbWVzKG5vdmVsdHlfdGFibGUpIDwtIGMoIm5vdmVsdHkiLCJVc2VySUQiKQ0KICBub3ZlbHR5X3RhYmxlIDwtIG5vdmVsdHlfdGFibGUgJT4lIHNlbGVjdChVc2VySUQsbm92ZWx0eSkgIyBub3ZlbHR5IHRhYmxlDQogIA0KICAjIyMgcmVzdWx0IG9mIGFjY3VyYWN5LCBjb3ZlcmFnZSwgYW5kIG5vdmVsdHkNCiAgbXlfbGlzdCA8LSBsaXN0KCJhY2N1cmFjeSIgPSBhY2NfSUJDRiwiY292ZXJhZ2UiID0gY292ZXJhZ2UsICJub3ZlbHR5IiA9IG5vdmVsdHlfdGFibGUpDQogIHJldHVybihteV9saXN0KSANCn0NCg0KDQp0ZXN0IDwtIGNhbGNfdG9wbl9tZXRyaWNzKG14X3JlZHVjZWQsMC44LDIwKQ0KDQp0ZXN0JGFjY3VyYWN5O3Rlc3QkY292ZXJhZ2U7IHRlc3Qkbm92ZWx0eQ0KDQpgYGANCjExIEltcGxlbWVudGllcnVuZyBUb3AtTiBNb25pdG9yIEF1ZmdhYmUgRElZOiBVbnRlcnN1Y2hlIGRpZSByZWxhdGl2ZSDDnGJlcmVpbnN0aW1tdW5nIHp3aXNjaGVuIFRvcC1OIEVtcGZlaGx1bmdlbiB1bmQgcHLDpGZlcmllcnRlbiBGaWxtZW4gZsO8ciA0IHVudGVyc2NoaWVkbGljaGUgTW9kZWxsZSAoei5CLiBJQkNGIHVuZCBVQkNGIG1pdCB1bnRlcnNjaGllZGxpY2hlbiDDhGhubGljaGtlaXRzLW1ldHJpa2VuIC8gTmFjaGJhcnNjaGFmdGVuIHNvd2llIFNWRCBtaXQgdW50ZXJzY2hpZWRsaWNoZXIgRGltZW5zaW9uYWxpdMOkdHNyZWR1a3Rpb24pLg0KDQoxMS4xIEZpeGllcmUgMjAgenVmw6RsbGlnIGdld8OkaGx0ZSBUZXN0a3VuZGVuIGbDvHIgYWxsZSBNb2RlbGx2ZXJnbGVpY2hlLA0KYGBge3J9DQpzZXQuc2VlZCg1NzgpDQp0cmFpbl90ZXN0XzExIDwtIGV2YWx1YXRpb25TY2hlbWUocnJtX3JlZHVjZWQsIG1ldGhvZD0ic3BsaXQiLCB0cmFpbj0wLjk1LCBrPTEsIGdpdmVuPTIwLGdvb2RSYXRpbmc9NCkgDQoNCiMgdHJhaW5pbmcgZGF0YXNldCBoYXMgMzgwIHVzZXJzLHRlc3QgZGF0YXNldCBoYXMgMjAgdXNlcnMgDQojIGdpdmVuPTIwOiBGb3IgZWFjaCB0ZXN0IHVzZXIsIDIwIGZpbG1zIHBlciB1c2VyIHdpbGwgYmUgdXNlZCBmb3IgcHJlZGljdGlvbiwgdGhlIHJlc3QgZm9yIGV2YWx1YXRpb24pDQpycm1fcmVkdWNlZF90cmFpbl8xMSA8LSBnZXREYXRhKHRyYWluX3Rlc3RfMTEsInRyYWluIikNCnJybV9yZWR1Y2VkX2tub3duXzExIDwtIGdldERhdGEodHJhaW5fdGVzdF8xMSwia25vd24iKSANCnJybV9yZWR1Y2VkX3Vua25vd25fMTEgPC0gZ2V0RGF0YSh0cmFpbl90ZXN0XzExLCJ1bmtub3duIikNCg0KIyBJQ0JGIG1vZGVscw0KbW9kZWxfSUJDRl9jb3NfMTAgPC1SZWNvbW1lbmRlcihkYXRhID0gcnJtX3JlZHVjZWRfdHJhaW5fMTEsbWV0aG9kPSJJQkNGIixwYXJhbWV0ZXI9bGlzdChub3JtYWxpemUgPSAiWi1zY29yZSIsbWV0aG9kPSJDb3NpbmUiLGs9MTApKQ0KbW9kZWxfSUJDRl9jb3NfNTAgPC1SZWNvbW1lbmRlcihkYXRhID0gcnJtX3JlZHVjZWRfdHJhaW5fMTEsbWV0aG9kPSJJQkNGIixwYXJhbWV0ZXI9bGlzdChub3JtYWxpemUgPSAiWi1zY29yZSIsbWV0aG9kPSJDb3NpbmUiLGs9NTApKQ0KDQptb2RlbF9JQkNGX3BzXzEwIDwtUmVjb21tZW5kZXIoZGF0YSA9IHJybV9yZWR1Y2VkX3RyYWluXzExLG1ldGhvZD0iSUJDRiIscGFyYW1ldGVyPWxpc3Qobm9ybWFsaXplID0gIlotc2NvcmUiLG1ldGhvZD0iUGVhcnNvbiIsaz0xMCkpDQptb2RlbF9JQkNGX3BzXzUwIDwtUmVjb21tZW5kZXIoZGF0YSA9IHJybV9yZWR1Y2VkX3RyYWluXzExLG1ldGhvZD0iSUJDRiIscGFyYW1ldGVyPWxpc3Qobm9ybWFsaXplID0gIlotc2NvcmUiLG1ldGhvZD0iUGVhcnNvbiIsaz01MCkpDQoNCiMgVUJDRiBtb2RlbHMNCm1vZGVsX1VCQ0ZfY29zXzEwIDwtUmVjb21tZW5kZXIoZGF0YSA9IHJybV9yZWR1Y2VkX3RyYWluXzExLG1ldGhvZD0iVUJDRiIscGFyYW1ldGVyPWxpc3Qobm9ybWFsaXplID0gIlotc2NvcmUiLG1ldGhvZD0iQ29zaW5lIixubj0xMCkpDQptb2RlbF9VQkNGX2Nvc181MCA8LVJlY29tbWVuZGVyKGRhdGEgPSBycm1fcmVkdWNlZF90cmFpbl8xMSxtZXRob2Q9IlVCQ0YiLHBhcmFtZXRlcj1saXN0KG5vcm1hbGl6ZSA9ICJaLXNjb3JlIixtZXRob2Q9IkNvc2luZSIsbm49NTApKQ0KDQptb2RlbF9VQkNGX3BzXzEwIDwtUmVjb21tZW5kZXIoZGF0YSA9IHJybV9yZWR1Y2VkX3RyYWluXzExLG1ldGhvZD0iVUJDRiIscGFyYW1ldGVyPWxpc3Qobm9ybWFsaXplID0gIlotc2NvcmUiLG1ldGhvZD0iUGVhcnNvbiIsbm49MTApKQ0KbW9kZWxfVUJDRl9wc181MCA8LVJlY29tbWVuZGVyKGRhdGEgPSBycm1fcmVkdWNlZF90cmFpbl8xMSxtZXRob2Q9IlVCQ0YiLHBhcmFtZXRlcj1saXN0KG5vcm1hbGl6ZSA9ICJaLXNjb3JlIixtZXRob2Q9IlBlYXJzb24iLG5uPTUwKSkNCg0KIyBTVkQgbW9kZWxzDQptb2RlbF9TVkRfMTAgPC0gUmVjb21tZW5kZXIoZGF0YSA9IHJybV9yZWR1Y2VkX3RyYWluXzExLG1ldGhvZD0iU1ZEIixwYXJhbWV0ZXI9bGlzdChub3JtYWxpemUgPSAiWi1zY29yZSIsaz0xMCkpDQptb2RlbF9TVkRfNTAgPC0gUmVjb21tZW5kZXIoZGF0YSA9IHJybV9yZWR1Y2VkX3RyYWluXzExLG1ldGhvZD0iU1ZEIixwYXJhbWV0ZXI9bGlzdChub3JtYWxpemUgPSAiWi1zY29yZSIsaz01MCkpDQoNCiMgZXZhbHVhdGlvbiBvZiB0aGUgcHJlZGljdGlvbnMNCmFjY19JQkNGX2Nvc18xMCA8LSBjYWxjUHJlZGljdGlvbkFjY3VyYWN5KHByZWRpY3Qob2JqZWN0ID0gbW9kZWxfSUJDRl9jb3NfMTAsIG5ld2RhdGEgPSBycm1fcmVkdWNlZF9rbm93bl8xMSwgbiA9IDE1LHR5cGU9InRvcE5MaXN0IikscnJtX3JlZHVjZWRfdW5rbm93bl8xMSxnaXZlbj0yMCxnb29kUmF0aW5nID0gNCkNCmFjY19JQkNGX2Nvc181MCA8LSBjYWxjUHJlZGljdGlvbkFjY3VyYWN5KHByZWRpY3Qob2JqZWN0ID0gbW9kZWxfSUJDRl9jb3NfNTAsIG5ld2RhdGEgPSBycm1fcmVkdWNlZF9rbm93bl8xMSwgbiA9IDE1LHR5cGU9InRvcE5MaXN0IikscnJtX3JlZHVjZWRfdW5rbm93bl8xMSxnaXZlbj0yMCxnb29kUmF0aW5nID0gNCkNCmFjY19JQkNGX3BzXzEwIDwtIGNhbGNQcmVkaWN0aW9uQWNjdXJhY3kocHJlZGljdChvYmplY3QgPSBtb2RlbF9JQkNGX3BzXzEwLCBuZXdkYXRhID0gcnJtX3JlZHVjZWRfa25vd25fMTEsIG4gPSAxNSx0eXBlPSJ0b3BOTGlzdCIpLHJybV9yZWR1Y2VkX3Vua25vd25fMTEsZ2l2ZW49MjAsZ29vZFJhdGluZyA9IDQpDQphY2NfSUJDRl9wc181MCA8LSBjYWxjUHJlZGljdGlvbkFjY3VyYWN5KHByZWRpY3Qob2JqZWN0ID0gbW9kZWxfSUJDRl9wc181MCwgbmV3ZGF0YSA9IHJybV9yZWR1Y2VkX2tub3duXzExLCBuID0gMTUsdHlwZT0idG9wTkxpc3QiKSxycm1fcmVkdWNlZF91bmtub3duXzExLGdpdmVuPTIwLGdvb2RSYXRpbmcgPSA0KQ0KDQphY2NfVUJDRl9jb3NfMTAgPC0gY2FsY1ByZWRpY3Rpb25BY2N1cmFjeShwcmVkaWN0KG9iamVjdCA9IG1vZGVsX1VCQ0ZfY29zXzEwLCBuZXdkYXRhID0gcnJtX3JlZHVjZWRfa25vd25fMTEsIG4gPSAxNSx0eXBlPSJ0b3BOTGlzdCIpLHJybV9yZWR1Y2VkX3Vua25vd25fMTEsZ2l2ZW49MjAsZ29vZFJhdGluZyA9IDQpDQphY2NfVUJDRl9jb3NfNTAgPC0gY2FsY1ByZWRpY3Rpb25BY2N1cmFjeShwcmVkaWN0KG9iamVjdCA9IG1vZGVsX1VCQ0ZfY29zXzUwLCBuZXdkYXRhID0gcnJtX3JlZHVjZWRfa25vd25fMTEsIG4gPSAxNSx0eXBlPSJ0b3BOTGlzdCIpLHJybV9yZWR1Y2VkX3Vua25vd25fMTEsZ2l2ZW49MjAsZ29vZFJhdGluZyA9IDQpDQphY2NfVUJDRl9wc18xMCA8LSBjYWxjUHJlZGljdGlvbkFjY3VyYWN5KHByZWRpY3Qob2JqZWN0ID0gbW9kZWxfVUJDRl9wc18xMCwgbmV3ZGF0YSA9IHJybV9yZWR1Y2VkX2tub3duXzExLCBuID0gMTUsdHlwZT0idG9wTkxpc3QiKSxycm1fcmVkdWNlZF91bmtub3duXzExLGdpdmVuPTIwLGdvb2RSYXRpbmcgPSA0KQ0KYWNjX1VCQ0ZfcHNfNTAgPC0gY2FsY1ByZWRpY3Rpb25BY2N1cmFjeShwcmVkaWN0KG9iamVjdCA9IG1vZGVsX1VCQ0ZfcHNfNTAsIG5ld2RhdGEgPSBycm1fcmVkdWNlZF9rbm93bl8xMSwgbiA9IDE1LHR5cGU9InRvcE5MaXN0IikscnJtX3JlZHVjZWRfdW5rbm93bl8xMSxnaXZlbj0yMCxnb29kUmF0aW5nID0gNCkNCg0KYWNjX1NWRF8xMCA8LSBjYWxjUHJlZGljdGlvbkFjY3VyYWN5KHByZWRpY3Qob2JqZWN0ID0gbW9kZWxfU1ZEXzEwLCBuZXdkYXRhID0gcnJtX3JlZHVjZWRfa25vd25fMTEsIG4gPSAxNSx0eXBlPSJ0b3BOTGlzdCIpLHJybV9yZWR1Y2VkX3Vua25vd25fMTEsZ2l2ZW49MjAsZ29vZFJhdGluZyA9IDQpDQphY2NfU1ZEXzUwIDwtIGNhbGNQcmVkaWN0aW9uQWNjdXJhY3kocHJlZGljdChvYmplY3QgPSBtb2RlbF9TVkRfNTAsIG5ld2RhdGEgPSBycm1fcmVkdWNlZF9rbm93bl8xMSwgbiA9IDE1LHR5cGU9InRvcE5MaXN0IikscnJtX3JlZHVjZWRfdW5rbm93bl8xMSxnaXZlbj0yMCxnb29kUmF0aW5nID0gNCkNCg0KYWNjX3RhYmxlIDwtIHJiaW5kKGFjY19JQkNGX2Nvc18xMCxhY2NfSUJDRl9jb3NfNTAsYWNjX0lCQ0ZfcHNfMTAsYWNjX0lCQ0ZfcHNfNTAsYWNjX1VCQ0ZfY29zXzEwLGFjY19VQkNGX2Nvc181MCxhY2NfVUJDRl9wc18xMCxhY2NfVUJDRl9wc181MCxhY2NfU1ZEXzEwLGFjY19TVkRfNTApDQoNCmFjY190YWJsZQ0KYGBgDQojIyMgSW4gdGhlIElCQ0YgbW9kZWwsIGJvdGggcHJlY2lzaW9uIGFuZCByZWNhbGwgYXJlIGJldHRlciB3aXRoIGNvc2luZSBtZXRob2QgYW5kIDUwIG5laWdoYm9ycy4NCiMjIyBJbiB0aGUgVUJDRiBtb2RlbCwgY29zaW5lIG1ldGhvZCBhbmQgMTAgbmVpZ2hib3JzIGlzIGEgYmV0dGVyIGNvbWJpbmF0aW9uLg0KIyMjIEluIHRoZSBTVkQgbW9kZWwsIHByZWNpc2lvbiBhbmQgcmVjYWxsIGFyZSBiZXR0ZXIgd2l0aCBzaW5ndWxhciB2YWx1ZSBvZiAxMC4gDQojIyMgVGhyb3VnaCBhbGwgdGhlIG1vZGVscywgVGhlIFNWRCBtb2RlbCB3aXRoIHNpbmd1bGFyIHZhbHVlIG9mIDEwIGhhcyB0aGUgYmVzdCBwcmVjaXNpb24gKDAuNDYzKSBhbmQgcmVjYWxsICgwLjA3NzkpLg0KDQoNCg0KMTEuMiBCZXN0aW1tZSBkZW4gQW50ZWlsIGRlciBUb3AtTiBFbXBmZWhsdW5nIG5hY2ggR2VucmVzIHBybyBLdW5kZSwNCg0KYGBge3J9DQpUb3Bfbl9nZW5yZSA8LSBmdW5jdGlvbihUb3Bfbl9saXN0LG4peyAgICMgbXggaXMgdXNlci1pdGVtIG1hdHJpeDsgVG9wX25fbGlzdDogdG9wLW4gbWF0cml4OyBuOiB0aGUgIm4iIGluIHRvcC1uIA0KICANCiAgdGFibGUgPSBkYXRhLmZyYW1lKCkNCiAgZm9yKGkgaW4gMTpkaW0oVG9wX25fbGlzdClbMl0pew0KICAgIGRmX3RvcCA8LSBhcy5kYXRhLmZyYW1lKFRvcF9uX2xpc3RbLGldKQ0KICAgIGNvbG5hbWVzKGRmX3RvcCkgPC0gIkZpbG0iDQogICAgDQogICAgZGZfZmlsbV9nZW5yZV8xIDwtIGFzLmRhdGEuZnJhbWUobXhfZmlsbV9nZW5yZSkNCiAgICBkZl9maWxtX2dlbnJlXzEkRmlsbSA8LSByb3duYW1lcyhkZl9maWxtX2dlbnJlXzEpDQogICAgDQogICAgZGZfdG9wIDwtIGxlZnRfam9pbihkZl90b3AsZGZfZmlsbV9nZW5yZV8xLGJ5PSgiRmlsbSIpKSAlPiUgc2VsZWN0KC1GaWxtKQ0KICAgIGRmX3RvcCA8LSBkZl90b3BbLTEsXSANCiAgICB0b3RhbCA8LSBzdW0oZGZfdG9wKQ0KICAgIGRmX3RvcFsicmF0aW8iLF0gPC0gY29sU3VtcyhkZl90b3ApL3RvdGFsDQogICAgZGZfdG9wIDwtIGRmX3RvcFsicmF0aW8iLF0NCg0KICAgIHRhYmxlIDwtIHJiaW5kKHRhYmxlLGRmX3RvcCkNCiAgfQ0KICByb3duYW1lcyh0YWJsZSkgPC0gY29sbmFtZXMoVG9wX25fbGlzdCkNCiAgcmV0dXJuKHRhYmxlKQ0KfQ0KDQoNCiMgVG9wLTE1IHJlY29tbWVuZGF0aW9uIGxpc3Qgb2YgU1ZEIHdpdGggayA9IDEwDQpQcmVkX1NWRF9rMTAgPC0gcHJlZGljdChvYmplY3QgPSBtb2RlbF9TVkRfMTAsIG5ld2RhdGEgPSBycm1fcmVkdWNlZF9rbm93bl8xMSwgbiA9IDE1LHR5cGU9YygidG9wTkxpc3QiKSkNClRvcDE1X1NWRCA8LSBzYXBwbHkoUHJlZF9TVkRfazEwQGl0ZW1zLCBmdW5jdGlvbih4KSB7Y29sbmFtZXMoZGZfcmVkdWNlZClbeF19KQ0KDQpUb3BfMTVfcmVjb21tZW5kYXRpb25zIDwtIFRvcF9uX2dlbnJlKFRvcDE1X1NWRCwxNSkgIyB0aGUgcGVyY2VudGFnZSBvZiB0b3AtMTUgcmVjb21tZW5kYXRpb25zIGJ5IGdlbnJlIHBlciB0ZXN0IHVzZXINCg0KVG9wXzE1X3JlY29tbWVuZGF0aW9ucztzdW1tYXJ5KHJvd1N1bXMoVG9wXzE1X3JlY29tbWVuZGF0aW9ucykpWy00XSAjIGNoZWNrIGlmIHRoZSB0b3RhbCBnZW5yZSByYXRpbyBmb3IgZWFjaCB1c2VyID0gMQ0KDQpgYGANCiMjIyBUaGUgdGFibGUgc2hvd3MgdGhlIHBlcmNlbnRhZ2Ugb2YgZ2VucmVzIGluIHRoZSB0b3AtMTUgcmVjb21tZW5kYXRpb24gbGlzdCBwZXIgdXNlci4NCiMjIyBUaGUgc3VtIG9mIGVhY2ggcm93IGFyZSBhbGwgMSwgdGhpcyBpbmRpY2F0ZXMgdGhlIHRvdGFsIHJhdGlvIG9mIGVhY2ggdXNlciBhcmUgYWxsIGNvcnJlY3QuIA0KDQoNCg0KMTEuMyBCZXN0aW1tZSBwcm8gS3VuZGUgZGVuIEFudGVpbCBuYWNoIEdlbnJlcyBzZWluZXIgVG9wLUZpbG1lICg9RmlsbWUsIHdlbGNoZSB2b20gS3VuZGVuIGRpZSBiZXN0ZW4gQmV3ZXJ0dW5nZW4gZXJoYWx0ZW4gaGFiZW4pDQoNCmBgYHtyfQ0KVG9wX2ZpbG1fZ2VucmUgPC0gZnVuY3Rpb24obXgsbil7ICAgIyBteCBpcyB1c2VyLWl0ZW0gbWF0cml4LCBuOiB0b3AtbiByYXRlZCBmaWxtcw0KICANCiAgdGFibGUgPSBkYXRhLmZyYW1lKCkNCiAgZm9yKGkgaW4gMTpkaW0obXgpWzFdKXsNCiAgICBkZl90b3AgPC0gYXMuZGF0YS5mcmFtZSh0KG14KSkNCiAgICBkZl90b3AkRmlsbSA8LSByb3duYW1lcyhkZl90b3ApDQogICAgZGZfdG9wIDwtIGRmX3RvcFssYyhpLChkaW0obXgpWzFdKzEpKV0NCiAgICBjb2xuYW1lcyhkZl90b3ApIDwtIGMoIlJhdGluZ3MiLCJGaWxtIikNCiAgICBkZl90b3AgPC0gZGZfdG9wICU+JSBmaWx0ZXIoY29tcGxldGUuY2FzZXMoLikpICU+JSBhcnJhbmdlKGRlc2MoUmF0aW5ncykpICU+JSBzbGljZSgxOm4pDQogICAgDQogICAgZGZfZmlsbV9nZW5yZV8xIDwtIGFzLmRhdGEuZnJhbWUobXhfZmlsbV9nZW5yZSkNCiAgICBkZl9maWxtX2dlbnJlXzEkRmlsbSA8LSByb3duYW1lcyhkZl9maWxtX2dlbnJlXzEpDQogICAgDQogICAgZGZfbGVmdF9qb2luIDwtIGxlZnRfam9pbihkZl90b3AsZGZfZmlsbV9nZW5yZV8xLGJ5PSgiRmlsbSIpKQ0KICAgIA0KICAgIGRmX3RvcCA8LSBkZl9sZWZ0X2pvaW5bLC0oMToyKV0gDQogICAgdG90YWwgPC0gc3VtKGRmX3RvcCkNCiAgICBkZl90b3BbInJhdGlvIixdIDwtIGNvbFN1bXMoZGZfdG9wKS90b3RhbA0KICAgIGRmX3RvcCA8LSBkZl90b3BbInJhdGlvIixdDQogICAgdGFibGUgPC0gcmJpbmQodGFibGUsZGZfdG9wKQ0KICB9DQogIHJvd25hbWVzKHRhYmxlKSA8LSByb3duYW1lcyhteCkNCiAgcmV0dXJuKHRhYmxlKQ0KfQ0KDQpUb3BfMTVfZmlsbXMgPC0gVG9wX2ZpbG1fZ2VucmUobXhfcmVkdWNlZCwxNSkgIyBnZW5yZXMgcHJvcG9ydGlvbiBvZiB0aGUgdG9wIDE1IGZpbG1zIGZvciBldmVyeSB1c2VyDQpUb3BfMTVfZmlsbXMNCmBgYA0KYGBge3J9DQpzdW1tYXJ5KHJvd1N1bXMoVG9wXzE1X2ZpbG1zKSlbLTRdDQpgYGANCiMjIyBUaGUgZmlyc3QgdGFibGUgc2hvd3MgdGhlIHBlcmNlbnRhZ2Ugb2YgZ2VucmVzIGluIHRoZSB0b3AtMTUgcmF0ZWQgbGlzdCBwZXIgdXNlci4NCiMjIyBUaGUgc3VtIG9mIGVhY2ggcm93IGFyZSBhbGwgMSwgdGhpcyBpbmRpY2F0ZXMgdGhlIHRvdGFsIHJhdGlvIG9mIGVhY2ggdXNlciBhcmUgYWxsIGNvcnJlY3QuIA0KDQoNCg0KMTEuNCBWZXJnbGVpY2hlIHBybyBLdW5kZSBUb3AtRW1wZmVobHVuZ2VuIHVuZCBUb3AtRmlsbWVuIG5hY2ggR2VucmVzLCANCg0KYGBge3J9DQojIGZpbHRlciB0aGUgVG9wLUZpbG1lbiB3aXRoIHRoZSB1c2VycyBvbmx5IGFwcGVhciBpbiB0aGUgVG9wLXJlY29tbWVuZGF0aW9uDQpUb3BfMTVfZmlsbXNfcmVkdWNlZCA8LSBUb3BfMTVfZmlsbXMNClRvcF8xNV9maWxtc19yZWR1Y2VkJFVzZXJJRCA8LSByb3duYW1lcyhUb3BfMTVfZmlsbXNfcmVkdWNlZCkNClRvcF8xNV9maWxtc19yZWR1Y2VkIDwtIFRvcF8xNV9maWxtc19yZWR1Y2VkICU+JSBmaWx0ZXIoVXNlcklEICVpbiUgcm93bmFtZXMoVG9wXzE1X3JlY29tbWVuZGF0aW9ucykpICU+JSBzZWxlY3QoLVVzZXJJRCkgIyB3aXRoIDIwIHVzZXJzDQoNCiMgY2FsY3VsYXRlIHRoZSBtZWFuIGFic29sdXRlIGVycm9yDQpNQUVfdG9wX2dlbnJlIDwtIHJvd1N1bXMoYWJzKFRvcF8xNV9maWxtc19yZWR1Y2VkIC0gVG9wXzE1X3JlY29tbWVuZGF0aW9ucykpLzIwDQoiTUFFIGJldHdlZW4gVG9wLXJlY29tbWVuZGF0aW9ucyBhbmQgVG9wLWZpbG1zIGJ5IGdlbnJlcyBwZXIgdXNlcjoiOyBNQUVfdG9wX2dlbnJlOyJ0aGUgZml2ZSBudW1iZXIgc3RhdGlzdGljcyBvZiB0aGUgTUFFOiI7c3VtbWFyeShNQUVfdG9wX2dlbnJlKVstNF0NCmBgYA0KDQoNCmBgYHtyfQ0KIk1TRSBiZXR3ZWVuIFRvcC1yZWNvbW1lbmRhdGlvbnMgYW5kIFRvcC1maWxtcyBieSBnZW5yZXMgcGVyIHVzZXI6Ig0KTVNFX3RvcF9nZW5yZSA8LSByb3dTdW1zKChUb3BfMTVfZmlsbXNfcmVkdWNlZCAtIFRvcF8xNV9yZWNvbW1lbmRhdGlvbnMpXjIpLzIwDQpNU0VfdG9wX2dlbnJlOyJ0aGUgZml2ZSBudW1iZXIgc3RhdGlzdGljcyBvZiB0aGUgTVNFOiI7c3VtbWFyeShNU0VfdG9wX2dlbnJlKVstNF0NCmBgYA0KDQoNCmBgYHtyfQ0KIlJNU0UgYmV0d2VlbiBUb3AtcmVjb21tZW5kYXRpb25zIGFuZCBUb3AtZmlsbXMgYnkgZ2VucmVzIHBlciB1c2VyOiINClJNU0VfdG9wX2dlbnJlIDwtIHNxcnQocm93U3VtcygoVG9wXzE1X2ZpbG1zX3JlZHVjZWQgLSBUb3BfMTVfcmVjb21tZW5kYXRpb25zKV4yKS8yMCkNClJNU0VfdG9wX2dlbnJlOyJ0aGUgZml2ZSBudW1iZXIgc3RhdGlzdGljcyBvZiB0aGUgUk1TRToiO3N1bW1hcnkoUk1TRV90b3BfZ2VucmUpWy00XQ0KDQpgYGANCiMjIyBUaHJlZSBxdWFudGl0YXRpdiBtZXRyaWNzIE1BRShtZWFuIGF2ZXJhZ2UgZXJyb3IpLCBNU0UobWVhbiBzcXVhcmVkIGVycm9yKSwgUk1TRSh0aGUgcm9vdCBtZWFuIHNxdWFyZWQgZXJyb3IpIHdlcmUgdXNlZCB0byBjb21wYXJlIHRoZSBkaWZmZXJlbmNlIGJldHdlZW4gdGhlIHRvcC1yZWNvbW1lbmRhdGlvbnMgYW5kIHRvcC1yYXRlZC1maWxtcyBieSBnZW5yZXMuDQoNCg0KDQoxMS41IERlZmluaWVyZSBlaW5lIFF1YWxpdMOkdHNtZXRyaWsgZsO8ciBUb3AtTiBMaXN0ZW4gdW5kIHRlc3RlIHNpZS4gDQoNCmBgYHtyfQ0KIyBNQVA6IEF2ZXJhZ2UgUHJlY2lzaW9uIGFuZCBNZWFuIEF2ZXJhZ2UgUHJlY2lzaW9uDQoNCk1BUCA8LSBmdW5jdGlvbihteCxUb3Bfbl9saXN0LG4pew0KICAjIGV4dHJhY3QgdGhlIHVzZXJzIGluIHRoZSBUb3AtbiBsaXN0cywgb3IgdXNlIGRpcmVjdCB0aGUgdGVzdCBkYXRhc2V0Lg0KICBteF9wYXJ0IDwtIGFzLmRhdGEuZnJhbWUobXgpICU+JSBmaWx0ZXIocm93bmFtZXMoYXMuZGF0YS5mcmFtZShteCkpICVpbiUgY29sbmFtZXMoYXMuZGF0YS5mcmFtZShUb3Bfbl9saXN0KSkpIyB1c2VyX2ZpbG0NCiAgbXhfcGFydCA8LSBhcy5kYXRhLmZyYW1lKHQobXhfcGFydCkpICMgdHJhbnNwb3NlIG14X3BhcnRfdXNlcnMgdG8gZmlsbV91c2VyDQogIG14X3BhcnQkRmlsbSA8LSByb3duYW1lcyhteF9wYXJ0KSAjIGdlbmVyYXRlIG5ldyBjb2x1bW4gIkZpbG0iIHNhbWUgYXMgdGhlIHJvd25hbWVzDQogIFRvcF9uX2xpc3QgPC0gYXMuZGF0YS5mcmFtZShUb3Bfbl9saXN0KQ0KICBUb3Bfbl9saXN0JFJhbmsgPC0gMTpuICMgZ2VuZXJhdGUgbmV3IGNvbHVtbiAiUmFuayIgdG8gcmVwcmVzZW50IHRoZSByYW5rcyBvZiB0aGUgcmVjb21tZW5kZWQgZmlsbXMNCiAgDQogIHN1bW1lX3ByZWNpc2lvbiA8LSAwDQogIGZvcihpIGluIChkaW0obXhfcGFydClbMl0tMSkpew0KICAgIFRvcF9pIDwtIFRvcF9uX2xpc3RbLGMoYWxsX29mKGkpLGRpbShUb3Bfbl9saXN0KVsyXSldICMgZXh0cmFjdCB0aGUgdG9wX25fbGlzdCBhbmQgcmFuayBvZiB0aGUgaS10aCB1c2VyDQogICAgY29sbmFtZXMoVG9wX2kpIDwtIGMoIkZpbG0iLCJSYW5rIikgIyByZW5hbWUgdGhlIGNvbHVtbnMgYXMgIkZpbG0iIGFuZCAiUmFuayINCiAgICBteF9pIDwtIG14X3BhcnQgJT4lIHNlbGVjdChjKGFsbF9vZihpKSxkaW0obXhfcGFydClbMl0pKSAgICAgICAjIG14X2k6IGV4dHJhY3QgdGhlIHJhdGluZ3MgYW5kIEZpbG0gbmFtZXMgb2YgaS10aCB1c2VyIGZyb20gcmF0aW5nIG1hdHJpeA0KICAgIGNvbG5hbWVzKG14X2kpIDwtIGMoIlJhdGluZyIsIkZpbG0iKQ0KICAgIG14X2pvaW4gPC0gbGVmdF9qb2luKFRvcF9pLG14X2ksYnk9IkZpbG0iKSAlPiUgZmlsdGVyKFJhdGluZz4zKSAjIGxlZnRfam9pbiB0aGUgcmF0aW5ncyB0byB0aGUgVG9wLW4gbGlzdCBieSAiRmlsbSIuIG14XzEgaGFzIHRoZSBjb2x1bW5zIG9mICJGaWxtIiwgIlJhbmsiLCBhbmQgcmF0aW5nczsgZmlsdGVyIHRoZSByZWxldmFudCBpdGVtcyAocmF0aW5ncyBncmVhdGVyIHRoYW4gMyk7IA0KICAgIG14X2pvaW4gPC0gbXhfam9pbiAlPiUgbXV0YXRlKE51bWVyYXRvciA9IDE6ZGltKG14X2pvaW4pWzFdLFByZWNpc2lvbiA9IE51bWVyYXRvci9SYW5rKSAjIGdlbmVyYXRlIG5ldyBjb2x1bW4gIk51bWVyYXRvciIgd2hpY2ggaXMgYSBuZXcgcmFuayBvbmx5IGZvciB0aGUgcmVsZXZhbnQgaXRlbXMsIGFuZCBuZXcgY29sdW1uICJQcmVjaXNpb24iIHdoaWNoIGlzIHRoZSBQcmVjaXNpb24gb2YgZXZlcnkgcmVsZXZhbnQgaXRlbXMuDQoNCiAgICBhdmdfdXNlcl9pX3ByZWNpc2lvbiA8LSBtZWFuKG14X2pvaW4kUHJlY2lzaW9uKSAgIyBhdmVyYWdlIHByZWNpc2lvbiBvZiB1c2VyLWkNCiAgICBzdW1tZV9wcmVjaXNpb24gPC0gc3VtbWVfcHJlY2lzaW9uICsgYXZnX3VzZXJfaV9wcmVjaXNpb24NCiAgfQ0KICBtYXAgPC0gc3VtbWVfcHJlY2lzaW9uLyhkaW0oVG9wX25fbGlzdClbMl0tMSkgIyBtZWFuIGF2ZXJhZ2UgcHJlY2lzaW9uDQogIHJldHVybihtYXApDQp9DQoNCk1BUChteF9yZWR1Y2VkLFRPUDE1X0lCQ0YsMTUpDQpgYGANCiMjIyBmaXJzdGx5LCBmb3Igb25lIHVzZXIsIGZpbmQgb3V0IHRoZSByYW5rIG9mIHRoZSBtLXRoIHJlbGV2YW50IGl0ZW0gKHJhdGluZyA+IDMpIGluIHRoZSB0b3Bfbl9saXN0LCB0aGVuIGNhbGN1bGF0ZSB0aGUgcHJlY2lzaW9uOiBtL24uDQojIyMgc2Vjb25kbHksIGNhbGN1bGF0ZSB0aGUgcHJlY2lzaW9ucyBvZiBhbGwgcmVsZXZhbnQgaXRlbXMuDQojIyMgdGhlIGF2ZXJhZ2UgcHJlY2lzaW9uIG9mIG9uZSB1c2VyOiBhdmVyYWdlIGFsbCB0aGUgcHJlY2lzaW9uIG9mIHJlbGV2YW50IGl0ZW1zLg0KIyMjIE1BUDogYXZlcmFnZSBwcmVjaXNpb24gb2YgYWxsIHVzZXJzLg==